題解 P2863 【[USACO06JAN]牛的舞會The Cow Prom】

題目連結

赤裸裸的闆子，就加一個特判就行。直接上代碼

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
bool ins[10000000];//記錄入沒入棧。
bool typ[10000000];//特判*1，是強連通分量就直接過了。
int top;int ans[10000000];
int stack[10000000];//手寫棧。
void push(int x)//手寫棧ing.
{
    ins[x]=true;
    stack[++top]=x;
    return ;
}
void pop()
{
    ins[stack[top]]=false;
    top--;
    return ;
}
struct data{
    int v;int next;
}edge[10000000];
int cnt;int alist[10000000];
void add(int u,int v)//繼續手寫結構體。
{
    edge[++cnt].v=v;
    edge[cnt].next=alist[u];
    alist[u]=cnt;
}
int dfn[100000];int dfu;//dfn作為x的入棧序号。
int low[1000000];int res=0;
void dfs(int x)//dfs
{
    dfn[x]=++dfu;//記錄搜尋序号
    push (x);
    low[x]=dfn[x];
    int next=alist[x];
    while(next)
    {
        int v=edge[next].v;
        if(ins[v]==true)//被搜過就不用再搜了
        {
            low[x]=min(low[x],low[v]);
        }
        else if(ins[v]==false)
        {
            dfs(v);
            low[x]=min(low[x],low[v]);
        }
        next=edge[next].next;
    }
    if(dfn[x]==low[x])//如果搜回來了。
    {
        while(low[stack[top]]==low[x])
        {
            typ[stack[top]]=true;
            pop();
            ans[x]++;
        }
        if(ans[x]>1) res++;//想要轉圈的話必須要兩個人及以上。
    }
    return;
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int n1,m1;
        scanf("%d%d",&n1,&m1);//不解釋。
        add(n1,m1);
    }
    for(int i=1;i<=n;i++)
    {
        if(typ[i]==1) continue;//要是在掃過的強連通分量裡面直接過。
        else dfs(i);
    }
    printf("%d",res);
    return 0;//程式拜拜
}