有向图+强联通分量

有向图+强联通分量

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<iostream>
using namespace std;
typedef long long  LL;
const double pi=acos(-1.0);
const double e=exp(1);
//const int MAXN =2e5+10;
const LL N = 100010*4;

vector<int > con[109], con1[109];
stack<int > qq;
int check[109], check1[109];
int dfn[109],low[109];
int captain[109], has[109];
int cnt = 0, num = 0, n;

void tarjian(int u)
{
    int i, v;

    qq.push(u);
    dfn[u] = low[u] = ++ cnt;
    check[u] = 1;

    for(i = 0; i < con[u].size(); i++)
    {
        v = con[u][i];
        if(!dfn[v])
        {
            tarjian(v);
            low[u] = min(low[u], low[v]);
        }
        else if(check[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(low[u] == dfn[u])
    {
        num ++;
        while(qq.top() != u)
        {
            //con1[num].push_back(qq.top());
            has[num] ++;
            captain[qq.top()] = num;

            check[qq.top()] = 0;
            qq.pop();
        }

    //	con1[num].push_back(qq.top());
        has[num] ++;
        captain[qq.top()] = num;

        check[qq.top()] = 0;
        qq.pop();
    }
}

void suodian()
{
    int i, j;
    for(i = 1; i <= n; i++)
    {
        for(j = 0; j < con[i].size(); j++)
        {
            if(captain[i] != captain[con[i][j]])
            {
                con1[ captain[i] ].push_back( captain[ con[i][j] ] );
            }
        }
    }
}

int main()
{
    int i, j, x, spot, ans, ans1;
    scanf("%d", &n);
    memset(dfn, 0, sizeof(dfn));
    memset(check, 0, sizeof(check));
    for(i = 1; i <= n; i++)
    {
        while(1)
        {
            scanf("%d", &x);
            if(x == 0)
                break;
            con[i].push_back(x);
        }
    }

    for(i = 1; i <= n; i++)
    {
        if(!dfn[i])
        {
            tarjian(i);
        }
    }

    suodian();

    ans = ans1 = 0;
    spot = 1;
    for(i = 1; i <= num; i++)
    {

        //cout << "i : " << i << " --> " << con[i].size() << endl;
        if(con1[i].size() == 0)
            ans1 ++;

        for(j = 0; j < con1[i].size(); j++)
        {
            check1[ con1[i][j] ] = 1;
        }
    }

    for(i = 1; i <= num; i++)
    {
        if(!check1[i])
            ans++;
    }

    ans1 = max(ans, ans1);
    if(num == 1)
        ans1 = 0;

    printf("%d\n%d\n", ans, ans1);

    return 0;
}

有向图+强联通分量

原文：https://www.cnblogs.com/daybreaking/p/12782865.html