题解 P2863 【[USACO06JAN]牛的舞会The Cow Prom】

· · 题解

刚刚才发现用vector做Tarjan很好用、、

其实这个题目就是一个Tarjan求强连通分量的裸题，本神犇在很早以前就已经写过强连通分量，但是发现这道题目的时候早就已经忘得一干二净了我靠( ‵o′)凸,I服了U!!

  1. 好了，不开玩笑了，其实用vector写Tarjan还是比较简单的，不用像各种图论题目一样写个add()建图，直接标记一下就可以用，像我这种懒得多一句都很难受的人，还是很适合我的么。。

  2. 其实这个题目跑完Tarjan之后判断一下cnt>1，成立的话就ans++，最后输出ans就可以了。

    粘一下代码：

    #include<cstdio>
#include<vector>
#define N 10010
using namespace std;
vector<int>g[N];
int color[N],dfn[N<<1],low[N<<1],stack[N<<1],vis[N],cnt[N],deep,top,n,m,sum,ans;
inline void tarjan(int u)
{

vis[u]=1;               //判断有没有访问过
stack[++top]=u;          //手动建立一个栈
dfn[u]=++deep;           //其实这两个才是最重要的，~~楼下大佬已经讲的够清楚了，本神犇就不多讲了~~
low[u]=deep;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
    int v=g[u][i];
    if(!dfn[v])
    {
        tarjan(v);
        low[u]=min(low[u],low[v]);
    }
    else
        if(vis[v])
            low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
    color[u]=++sum;
    vis[u]=0;
    while(stack[top]!=u)
    {
        color[stack[top]]=sum;
        vis[stack[top--]]=0;
    }
    top--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
    int a,b;
    scanf("%d%d",&a,&b);
    g[a].push_back(b);
}
for(int i=1;i<=n;i++)
    if(!dfn[i])
        tarjan(i);
for(int i=1;i<=n;i++)
    cnt[color[i]]++;
for(int i=1;i<=sum;i++)
    if(cnt[i]>1)
        ans++;
printf("%d",ans);
return 0;                //~~程序完美的结束，~~AC啦！！
}