POJ 2186 Popular Cows 强连通分量缩点处理

Online Judge	Problem Set	Authors	Online Contests	User
Web Board Home Page F.A.Qs Statistical Charts	Problems Submit Problem Online Status Prob.ID:	Register Update your info Authors ranklist	Current Contest Past Contests Scheduled Contests Award Contest	AshGuangr      Log Out Mail:2(0) Login Log      Archive

3 3
1 2
2 1
2 3

1

题目大意:有n头牛,m个关系,表示为A牛认为B牛厉害,A-B A-C A也能到C,问有几头牛可以被所有牛认为厉害

题目思路:

一个强连通分量里的所有牛绝对会被其他认为厉害.

首先这个有向图需要联通,不连通的话,根本不存在.  

其次 只要联通那么强连通分量之间具有单向关系,因为如果具有双向关系,是可以合并的.

所以 满足条件的点全部都在出度为0的强连通分量中.

1->2->3->4  那肯定选4 并且只能有一个出度为0 ,两个肯定还是不行.

具体代码:

//#include <bits/stdc++.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1000;
const int maxn=1e6+5;
const ll INF=100000000000005;
using namespace std;
ll n,m,p;
int head[maxn];
ll cnt=0;
struct node{
    int e,next;
}edge[maxn];
int dfn[maxn],low[maxn];//dfs序号 他能连接到的最小根节点
int st[maxn],s=0;//栈
int sct[maxn],szsc[maxn],scc=0;//强连通分量所属,强连通分量个数
int inst[maxn];//标记是否在栈中
int out[maxn];
int pre[maxn];
int cot=0;//标记DFS序
void addedge(int u,int v)
{
    edge[cnt].e=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void restart()
{
    memset(head,-1,sizeof(head));
    memset(low,0,sizeof(low));
    memset(inst,0,sizeof(inst));
    memset(dfn,0,sizeof(dfn));
    memset(out,0,sizeof(out));
    memset(szsc,0,sizeof(szsc));
    s=0;scc=0;cot=0;
    cnt=0;
}
void Tarjan(int u)
{
    st[++s]=u;inst[u]=1;
    low[u]=dfn[u]=++cot;
    for(int i=head[u];~i;i=edge[i].next)
    {
        int e=edge[i].e;
        if(!dfn[e]){
            Tarjan(e);
            low[u]=min(low[u],low[e]);
        }
        else if(inst[e]) low[u]=min(low[u],dfn[e]);
        //else 被访问过并且不在栈里 那肯定已经为强连通分量了
    }
    if(low[u]==dfn[u]){
        scc++;//强连通分量++
        while(1)
        {
            int x=st[s--];
            inst[x]=0;
            sct[x]=scc;
            szsc[scc]++;//强连通分量的大小为1
            if(u==x) break;
        }
    }
}
int Find(int x)
{
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}
void Merge(int x,int y)
{
    int dx=Find(x);
    int dy=Find(y);
    if(dx!=dy)
        pre[dx]=dy;
    return;
}
int main()
{
    while(~scanf("%lld%lld",&n,&m))
    {
        restart();
        for(int i=1;i<=n;i++) pre[i]=i;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,y);
            Merge(x,y);
        }
        for(int i=1;i<=n;i++)if(!dfn[i]) Tarjan(i);
        for(int i=1;i<=n;i++)
        {
            for(int k=head[i];~k;k=edge[k].next)
            {
                int e=edge[k].e;
                if(sct[i]!=sct[e]) out[sct[i]]++;
            }
        }
        int f=0;
        int x=Find(1);
        for(int i=1;i<=n;i++)//判联通
        {
            if(Find(i)!=x)
            {
                f=1;
                break;
            }
        }
        ll sum=0;
        int ok=0;
        for(int i=1;i<=scc;i++)
        {
            if(out[i]==0){
                ok++;
                sum+=szsc[i];
            }
        }
        if(ok==1&&!f) printf("%lld\n",sum);
        else printf("0\n");
    }
    return 0;
}
/***
样例测试空间:
6
5
1 2
2 3
3 1
3 5
2 6
***/

总结:开始图的连通性了.