POJ 2186 Popular Cows tarjan缩点算法

  题意:给出一个有向图代表牛和牛喜欢的关系,且喜欢关系具有传递性,求出能被所有牛喜欢的牛的总数(除了它自己以外的牛,或者它很自恋)。

  思路:这个的难处在于这是一个有环的图,对此我们可以使用tarjan算法求出强连通分量,把强连通分量压缩成一个点,构成一个新的图,这个图一定是没有环的,如果有环就跟强连通分量的矛盾了。压缩成无环图以后这个图里面的点是不具有方向的,我们通过遍历每个节点所能连到的点,如果两点的id值即所在的强连通分量区域不同时,我们就把这个节点的出度加1。最后去找那些出度等于0的点,如果没有或者超过1,那这图的答案是0,因为如果有两个点他们的出度都是0,那么意味着这两个点之间没有关系,所以地图中不可能出现一头牛被所有的牛喜欢。

  需要注意的地方,在一开始我的连通分量的id记录出错了,原因是我的第一个点在主函数里入栈,导致有些点没有被记录。后来受无向图的惯性思维的影响,又把判断pa != v的条件加上了,这个是有向图,是绝对不可以加这个判定的!具体代码如下:

#include<cstdio>
#include<stack>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn 10010
struct EDGE
{
int to,nxt;
} edge[maxn*];
int head[maxn],id[maxn],dfn[maxn],low[maxn],tot,sum;
stack<int> s;
int all[maxn];
void tarjan(int u,int fa)
{
s.push(u);
dfn[u] = low[u] = ++tot;
for(int i = head[u]; i != -; i = edge[i].nxt)
{
int v = edge[i].to;
if(!dfn[v])
{
tarjan(v,u);
low[u] = min(low[v],low[u]);
}
else if(!id[v]) low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u])
{
sum++;
while(!s.empty())
{
int num = s.top();
s.pop();
id[num] = sum;
all[sum]++;
if(u == num) break;
}
}
return ;
}
int main()
{
int n,m,x,y;
while(~scanf("%d%d",&n,&m))
{
memset(head,-,sizeof(head));
for(int i = ; i < m; i++)
{
scanf("%d%d",&x,&y);
edge[i].to = y;
edge[i].nxt = head[x];
head[x] = i;
}
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(id,,sizeof(id));
tot = ,sum = ;
while(!s.empty()) s.pop();
memset(all,,sizeof(all));
for(int i = ; i <= n; i++)
{
if(!dfn[i])
{
tarjan(i,-);
}
}
//cout<<"sum = "<<sum<<endl;
int vis[maxn];
memset(vis,,sizeof(vis));
int du[maxn];
memset(du,,sizeof(du));
/*for(int i = 1;i <= sum;i++)
{
cout<<"all = "<<all[i]<<endl;
}*/
for(int u = ; u <= n; u++)
{
for(int j = head[u]; j != -; j = edge[j].nxt)
{
int v = edge[j].to;
if(id[u] != id[v])
{
du[id[u]]++;
}
}
}
int sub = ,last = ;
for(int i = ; i <= sum; i++)
{
if(du[i] == )
{
sub++;
last = i;
}
}
if(sub != ) puts("");
else printf("%d\n",all[last]);
}
return ;
}
上一篇:Selenium 3----鼠标、键盘操作常用方法


下一篇:vijos P1780 【NOIP2012】 开车旅行