SCC：：poj2186 Popupar Cows poj2553 The Bottom of A Graph

本文主要是介绍SCC：：poj2186 Popupar Cows poj2553 The Bottom of A Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于SCC的知识与算法，参见《SCC》一文。这两道题本质是一样的，细微的区别只在于输出而已。夜鱼只给我做前一道题，大概是看到我做的《图算法》的小结里面没有SCC的地位，想给我提个醒。后来我在那篇小结里面补上了SCC，顺便也对SCC的知识梳理了一遍，觉得手痒，网上查了一下还有poj2553也是关于SCC的，但没想到poj2553一题是赤裸裸的SCC，但这道题我却WA了几次，原因是在输出的时候没有“按序”！

 1. poj2186"Popupar Cows"

题目大意：一次调查结果（A，B）表示牛A认为B受欢迎，这种关系具有传递性。有N（1~10000）头牛牛，做了M（0~50000）次调查。求被所有其他牛牛欢迎的牛的头数。

分析：画了图就知道，其实就是求最大连通分量图G^{SCC}，然后求该图每个“点”的出度，若出度为零的个数大于1，则无解，否则输出出度为零的“点”的内容。求SCC的时候选用的是tarjan算法。

#include "stdafx.h"       //Memory:1816k    Time:454ms
#include <iostream>
using namespace std;
#define MaxN 10010
#define MaxE 50010
//========================模板开始=====================================
typedef struct node{
int data;
struct node *next;
}SLink;
SLink to[MaxE];
int dfu[MaxN],low[MaxN]; //dfu[i]为节点i搜索的次序编号，low[i]为i或i的子树能够追溯到的最早的栈中节点的次序编号
int order[MaxN],SCC[MaxN]; //order记录遍历次序，SCC[i]记录i所属的SCC
int count[MaxN];        //记录每个SCC的出度
bool ifstack[MaxN];         //相当于栈的作用
int dex=0,st=0,cnt=0;
int N,M;
void tarjan(int i){
dfu[i]=low[i]=++dex;
ifstack[i]=1;     //i入栈
order[++st]=i;   //记录遍历顺序
int j;
for(SLink *e=&to[i];e;e=e->next){      //这个for为DFS
j=e->data;
if(!dfu[j]){
tarjan(j);
if(low[j]<low[i])
low[i]=low[j];
}
else if(ifstack[j] && dfu[j]<low[i])
low[i]=dfu[j];
}
if(dfu[i]==low[i]){  //当dfu(i)=low(i)时，以i为根的搜索子树上所有节点是一个强连通分量。
cnt++;
do{
j=order[st--];
ifstack[j]=0;
SCC[j]=cnt;
}while(j!=i);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cin>>N>>M;
for(int i=1;i<=N;i++){
to[i].data=i;
to[i].next=NULL;
}
int temp1,temp2;
for(int i=1;i<=M;i++){
cin>>temp1>>temp2;
SLink *p=new SLink;
p->data=temp2;
p->next=to[temp1].next;
to[temp1].next=p;
}
memset(dfu,0,sizeof(dfu));
for(int i=1;i<=N;i++){
if(!dfu[i])
tarjan(i);
}
memset(count,0,sizeof(count));
for(int i=1;i<=N;i++){
for(SLink *e=&to[i];e;e=e->next){
if(SCC[i]!=SCC[e->data])
count[SCC[i]]++;
}
}
//=========================模板结束======================================
int cow=0,k=1;
for(int i=1;i<=cnt;i++){
if(count[i]==0){         
cow++;k=i;
}
}
if(cow!=1) cout<<0<<endl;
else{
int num=0;
for(int i=1;i<=N;i++){
if(SCC[i]==k)
num++;
}
cout<<num<<endl;
}
return 0;
}

2. poj2553"The Bottom of A Graph"

赤裸裸的一道题，出题者大概是知道现在的文化潮流：快餐！连衣服都不穿。

借用poj2186的代码，其中“//======模板开始====……//=====模板结束=====”部分的代码一字不改，只是改写输出部分。一开始WA几次，觉得没道理，后来测了数据【10 1 1 5】就发现问题了，用了一个hash表排了下序，比较ugly地AC了。

…… ……                 // M:2396K        T:375MS
while((cin>>N) && N && (cin>>M)){
dex=st=cnt=0;
…… ……
int pri[MaxN]={0};
for(int i=1;i<=cnt;i++){
if(count[i]==0){
for(int k=1;k<=N;k++){
if(SCC[k]==i){
pri[k]=1;
}
}
}
}
for(int k=1;k<=N;k++){
if(pri[k]==1){
cout<<k<<" ";
}
}
cout<<endl;
}

3. 总结：

这些题目，模板性太强了，主体的算法一经写出来，剩下的就是一下细节上的处理了。相对与poj1112"team them up"来说，这两题很简单，poj1112的复杂之处在于求完SCC之后还要DP一下，甚为拐弯抹角。

 

这篇关于SCC：：poj2186 Popupar Cows poj2553 The Bottom of A Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---