POJ 1236 Network of Schools 有向图强连通分量

参考这篇博客:

http://blog.csdn.net/ascii991/article/details/7466278

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
using namespace std;
typedef long long LL;
const int N = 1e2+;
int head[N],tot,p,h[N],n,out[N],in[N];
struct Edge{
int u,v,next;
}edge[N*N],e[N*N];
void add(int u,int v){
edge[tot].u=u;
edge[tot].v=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void addedge(int u,int v){
e[p].v=v;
e[p].next=h[u];
h[u]=p++;
}
int clk,dfn[N],low[N],cnt,bel[N];
bool instack[N];
stack<int>s;
void targin(int u){
dfn[u]=low[u]=++clk;
s.push(u);
instack[u]=true;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].v;
if(!dfn[v]){
targin(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++cnt;
int k;
do{
k=s.top();
s.pop();
instack[k]=false;
bel[k]=cnt;
}while(k!=u);
}
}
int main(){
scanf("%d",&n);
memset(head,-,sizeof(head));
memset(h,-,sizeof(h));
for(int i=;i<=n;++i){
for(int x;;){
scanf("%d",&x);
if(!x)break;
add(i,x);
}
}
for(int i=;i<=n;++i)
if(!dfn[i])targin(i);
if(cnt==){
printf("1\n0\n");
return ;
}
for(int i=;i<tot;++i){
int k1=bel[edge[i].u],k2=bel[edge[i].v];
if(k1==k2)continue;
addedge(k1,k2);
++in[k2];
++out[k1];
}
int ans1=,ans2=;
for(int i=;i<=cnt;++i){
if(!in[i])++ans1;
if(!out[i])++ans2;
}
printf("%d\n%d\n",ans1,max(ans1,ans2));
return ;
}
上一篇:前端学PHP之变量


下一篇:JSP中的Servlet及Filter