| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 27496 | Accepted: 11059 |
Description
Input
Output
Sample Input
3 3 1 2 2 1 2 3
Sample Output
1
Hint
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define N 10000+10
#define M 51000+10
using namespace std;
int n, m;
struct node
{
int to;
int next;
}edge[M];//保证存下所有的边
int head[N], dfn[N], low[N], vis[N];
int stack[N], num[N], du[N];
int counter, top, cut, cnt;
/*
dfn[]:记录搜索时各顶点的访问次序，即深度优先数
low[u]:每个节点定义一个low值 low[u]是从u或u的子孙出发通过回边可以到达
的最低深度优先数
注意：dfn[]在搜索前进时进行统计 low[]值是在回退的时候进行计算
du[]:表示出度
*/
void init()
{
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(num, 0, sizeof(num));
memset(du, 0, sizeof(du));
counter=1;//begin 1
cnt=0;//边 计数
top=0;// stack top
cut=0;
}
void addedge(int u, int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}//静态数组 倒着建边
void dfs(int u)
{
dfn[u]=low[u]=counter++;//counter的值从1开始
vis[u]=1;//标记访问
stack[top++]=u;
//遍历从u节点发出的边
for(int i=head[u]; i!=-1; i=edge[i].next){
int v=edge[i].to;
if(!vis[v]){//这是一条树边
dfs(v);
low[u]=min(low[u], low[v]);//回溯的时候比较
}
else if(vis[v]){
low[u]=min(low[u], dfn[v]);
}
}
if(low[u]==dfn[u]){
cut++;//表示已经找到了一个强连通分量
while(top>0 && stack[top]!=u){
top--;
vis[stack[top]]=2;//
num[stack[top]]=cut;//确定当前这个节点属于哪个强连通分量
}
}
}
int main()
{
int i, j;
while(scanf("%d %d", &n, &m)!=EOF)
{
init();//进行初始化
int u, v;
for(i=1; i<=m; i++){
scanf("%d %d", &u, &v);
addedge(u, v);
}//建立单向边
for(i=1; i<=n; i++){
if(!vis[i]){
dfs(i);
}
}//不知道为什么在此处计数一下连通分量的数目 如果大于1 直接输出0 这样提交 会WA。不写就对
for(i=1; i<=n; i++){
for(j=head[i]; j!=-1; j=edge[j].next){
int v=edge[j].to;
if(num[i]!=num[v])//如果连通分量的编号不等
du[num[i]]++;//出度++
}
}
int pos; int dd=0;
for(i=1; i<=cut; i++){
if(du[i]==0){
dd++; pos=i;
}
}
//printf("pos = %d\n", pos);
if(dd==1){
int ans=0;
for(i=1; i<=n; i++){
if(num[i]==pos)
ans++;
}
printf("%d\n", ans );
}
else printf("0\n");
}
return 0;
}
使用STL-stack模拟的，注意在栈弹出节点的地方的写法，在循环跳出之后再弹出一次，因为遇到u==v的时候就跳出了，而u没有被弹出。
上面的数组模拟的stack操作也可以再修改一下。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stack>
#include <algorithm>
#define N 10000+10
#define M 51000+10
using namespace std;
int n, m;
struct node
{
int to;
int next;
}edge[M];//保证存下所有的边
int head[N], dfn[N], low[N], vis[N];
int num[N], du[N];
int counter, top, cut, cnt;
/*
dfn[]:记录搜索时各顶点的访问次序，即深度优先数
low[u]:每个节点定义一个low值 low[u]是从u或u的子孙出发通过回边可以到达
的最低深度优先数
注意：dfn[]在搜索前进时进行统计 low[]值是在回退的时候进行计算
du[]:表示出度
*/
stack<int>q;
void init()
{
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(num, 0, sizeof(num));
memset(du, 0, sizeof(du));
counter=1;//begin 1
cnt=0;//边 计数
top=0;// stack top
cut=0;
}
void addedge(int u, int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}//静态数组 倒着建边
void dfs(int u)
{
dfn[u]=low[u]=counter++;//counter的值从1开始
vis[u]=1;//标记访问
q.push(u);
//遍历从u节点发出的边
for(int i=head[u]; i!=-1; i=edge[i].next){
int v=edge[i].to;
if(!vis[v]){//这是一条树边
dfs(v);
low[u]=min(low[u], low[v]);//回溯的时候比较
}
else if(vis[v]){
low[u]=min(low[u], dfn[v]);
}
}
if(low[u]==dfn[u]){
cut++;//表示已经找到了一个强连通分量
while(!q.empty() && q.top()!=u){
vis[q.top()]=2;//
num[q.top()]=cut;//确定当前这个节点属于哪个强连通分量
q.pop();
}
vis[q.top()]=2;//
num[q.top()]=cut;//确定当前这个节点属于哪个强连通分量
q.pop(); //还要将u节点弹出
}
}
int main()
{
int i, j;
while(scanf("%d %d", &n, &m)!=EOF)
{
init();//进行初始化
int u, v;
for(i=1; i<=m; i++){
scanf("%d %d", &u, &v);
addedge(u, v);
}//建立单向边
int cur=0;
for(i=1; i<=n; i++){
if(!vis[i]){
dfs(i); cur++;
}
}
for(i=1; i<=n; i++){
for(j=head[i]; j!=-1; j=edge[j].next){
int v=edge[j].to;
if(num[i]!=num[v])//如果连通分量的编号不等
du[num[i]]++;//出度++
}
}
int pos; int dd=0;
for(i=1; i<=cut; i++){
if(du[i]==0){
dd++; pos=i;
}
}
if(dd==1){
int ans=0;
for(i=1; i<=n; i++){
if(num[i]==pos)
ans++;
}
printf("%d\n", ans );
}
else printf("0\n");
}
return 0;
}
poj 2186 Popular Cows 【强连通分量Tarjan算法 + 树问题】
原文：http://www.cnblogs.com/yspworld/p/4768709.html