hdu2767强连通加缩点

时间：2024-01-18 16:21:20

https://vjudge.net/contest/156688#problem/B

题目说了一大堆，前面的没有用，就是让你判断要加几条边才能强连通，用到缩点的知识

二重循环，判断邻接表下一个点是不是在强连通分量中，入度，出度分别保存下来，输出较大的那一个

#include<map>

#include<set>

#include<list>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 1000000007

using namespace std;

const int N=,maxn=,inf=0x3f3f3f3f;

int n,m;//判断是不是在栈中，2为在栈中，1为已访问不在栈中，0为不在栈中

stack<int>s;

vector<int>v[N],ans[N];

int dfn[N],low[N];

int inans[N],ins[N];

int num,index;

int in[N],out[N];

void tarjan(int u)

{

    ins[u]=;

    dfn[u]=low[u]=++index;

    s.push(u);

    for(int i=;i<v[u].size();i++)

    {

        int x=v[u][i];

        if(dfn[x]==)

        {

            tarjan(x);

            low[u]=min(low[u],low[x]);

        }

        else if(ins[x]==)low[u]=min(low[u],dfn[x]);

    }

    if(dfn[u]==low[u])

    {

        ++num;

        while(!s.empty()){

            int k=s.top();

            s.pop();

            ins[k]=;

            inans[k]=num;

            if(k==u)break;

        }

    }

}

int main()

{

    int t;

    cin>>t;

    while(t--){

        index=num=;

        memset(dfn,,sizeof(dfn));

        memset(low,,sizeof(low));

        memset(ins,,sizeof(ins));

        memset(in,,sizeof(in));

        memset(out,,sizeof(out));

        for(int i=;i<=n;i++)

        {

            v[i].clear();

            ans[i].clear();

        }

        while(!s.empty())s.pop();

        cin>>n>>m;

        while(m--){

            int a,b;

            cin>>a>>b;

            v[a].push_back(b);

        }

        for(int i=;i<=n;i++)

            if(!dfn[i])

               tarjan(i);

        if(num==)

        {

            cout<<<<endl;

            continue;

        }

        for(int i=;i<=n;i++)

        {

            for(int j=;j<v[i].size();j++)

            {

                int p=v[i][j];

                if(inans[i]==inans[p])continue;

                in[inans[i]]=out[inans[p]]=;

            }

        }

        int a=,b=;

        for(int i=;i<=num;i++)

        {

            if(!in[i])a++;

            if(!out[i])b++;

        }

        cout<<max(a,b)<<endl;

    }

    return ;

}

相关文章