HDU 2767 강 연통 축소 점

A 가 B 를 증명 할 수 있다 면 방향 A - > B 를 만 듭 니 다.서로 증명 할 수 있 는 집합 에 대해 서 는 반드시 두 점 마다 서로 도착 할 수 있다. 이런 집합 은 하나의 강력 한 연결 집합 이다.우 리 는 그들 을 하나의 점 으로 볼 수 있 고, 나머지 는 DAG 그림 이다.만약 서로 도착 할 수 있다 면, 각 점 마다 반드시 도 > = 1, 입도 > 1...그래서 통계 에 입 도 없 는 점 과 출 도 없 는 점 이 얼마나 있 는 지, 그들 중에서 가장 큰 것 은 추가 해 야 할 변 이다.
VIEW CODE

#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<set>
#include<ctime>
#include<cmath>
#define eps 1e-8
#define ex 2.7182818284590452354
#define pi acos(-1.0)
#define inf 0x3fffffff
#define DC(n) printf("Case #%d:",++n)
#define SD(n) scanf("%d",&n)
#define SS(str) scanf("%s",str)
#define SDB(n) scanf("%lf",&n)
#define ll long long
#define mm 1000000007
#define mmax  20010
using namespace std;
struct node
{
    int en;
    int next;
}E[50010];
int p[mmax];
int num;
void add(int st,int en)
{
    E[num].en=en;
    E[num].next=p[st];
    p[st]=num++;
}
void init()
{
    memset(p,-1,sizeof p);
    num=0;
}


int fa[mmax];
int dfn[mmax];
int low[mmax];
int times;
int Q[mmax];
int pp;

bool instack[mmax];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void tarjin(int u)
{

    dfn[u]=low[u]=++times;
    Q[++pp]=u;
    instack[u]=1;
    for(int i=p[u];i+1;i=E[i].next)
    {
        int v=E[i].en;
        if(!dfn[v])
        {
            tarjin(v);
            if(low[u]>low[v])
                low[u]=low[v];
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        while(pp)
        {
            int x=Q[pp--];
            instack[x]=0;
            if(x==u)
                break;
            int xx=find(x);
            fa[xx]=u;
        }
    }
}




int in[mmax];
int out[mmax];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        init();
        int n,m;
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            add(x,y);
        }
        memset(dfn,0,sizeof dfn);
        memset(instack,0,sizeof instack);
        times=0;
        pp=0;
        for(int i=1;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])
                tarjin(i);
        }
        memset(in,0,sizeof in);
        memset(out,0,sizeof out);
        for(int i=1;i<=n;i++)
        {
            int xx=find(i);
            for(int j=p[i];j+1;j=E[j].next)
            {
                int yy=find(E[j].en);
                if(xx!=yy)
                {
                    out[xx]++;
                    in[yy]++;
                }
            }
        }
        int cnt=0,cnt1=0,cnt2=0;
        for(int i=1;i<=n;i++)
        {
            if(fa[i]==i)
            {
                cnt++;
                if(out[i]==0)
                    cnt1++;
                if(in[i]==0)
                    cnt2++;
            }
        }
        int ans;
        if(cnt==1)
            ans=0;
        else
            ans=max(cnt1,cnt2);
        cout<<ans<<endl;
    }
}