poj1236 SCC+缩点

时间:2023-03-09 08:01:28
poj1236 SCC+缩点
/*
强连通分量内的点可以互相传送,可以直接缩点
缩点后得到一棵树
第一问的答案是零入度点数量,
第二问: 加多少边后变成强连通图
树上入度为0的点有p个,出度为0的点为q,那么答案就是max(p,q)
如果缩点后是一个点,答案就是0
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define maxn 105
struct Edge{int to,nxt;}edge[<<];
int n,head[maxn],tot;
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
} int dfn[maxn],low[maxn],stack[maxn],ins[maxn],c[maxn],cnt,top,ind;
void tarjan(int x){
low[x]=dfn[x]=++ind;
stack[++top]=x;
ins[x]=;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x]){
cnt++;
int y;
do{
y=stack[top--];
ins[y]=;
c[y]=cnt;
}while(y!=x);
}
}
void init(){
cnt=tot=ind=top=;
memset(dfn,,sizeof dfn);
memset(low,,sizeof low);
memset(stack,,sizeof stack);
memset(ins,,sizeof ins);
memset(c,,sizeof c);
memset(head,-,sizeof head);
}
int main(){
while(cin>>n){
init();
for(int i=;i<=n;i++){
int u=i,v;
while(scanf("%d",&v),v)
addedge(u,v);
}
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
if(cnt==){
printf("1\n0\n");
continue;
} //缩点
int in[maxn]={},out[maxn]={},p=,q=;
for(int x=;x<=n;x++)
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(c[x]==c[y])continue;
in[c[y]]++;out[c[x]]++;
}
for(int i=;i<=cnt;i++){
if(in[i]==)p++;
if(out[i]==)q++;
}
printf("%d\n%d\n",p,max(p,q));
}
}