Usaco Training Section 5.3 Network of Schools
tarjan缩点模板题
首先tarjan缩点一下,然后第一问直接输出入度为0的点的个数,因为这些点没有点可以到达。第二问要特判一下,如果原图已经是强连通分量,直接输出0。否则输出max(入度为0的点的个数,出度为0的点的个数),大概理解一下:这样之后,每个强连通分量都能够将文件传出去和传入,好像就可以了。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
const int M=10005,N=105;
struct edg{
int nxt,to;
}e[M<<1];
int head[N],cnt;
stack<int> s;
bool vis[N];
int ind[N],low[N],inde;
int tot,num[N],sz[N];
inline void add(int u,int v){
e[++cnt].nxt=head[u];head[u]=cnt;e[cnt].to=v;
}
inline void tarjan(int u){
ind[u]=low[u]=++inde;
s.push(u);
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!ind[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],ind[v]);
}
}
if(low[u]==ind[u]){
++tot;
int v=0;
while(v!=u){
v=s.top();
s.pop();
vis[v]=0;
num[v]=tot;
++sz[tot];
}
}
}
int ru[N],chu[N];
int main()
{
freopen("schlnet.in","r",stdin);
freopen("schlnet.out","w",stdout);
int n=read();
for(int i=1;i<=n;++i){
int x=read();
while(x!=0){
add(i,x);
x=read();
}
}
tot=0;
for(int i=1;i<=n;++i)
if(!ind[i]) tarjan(i);
if(tot==1){
puts("1");
puts("0");
return 0;
}
for(int i=1;i<=n;++i)
for(int j=head[i];j;j=e[j].nxt){
int v=e[j].to;
if(num[i]!=num[v]) ++ru[num[v]],++chu[num[i]];
}
int ru0=0,chu0=0;
for(int i=1;i<=tot;++i){
if(ru[i]==0) ++ru0;
if(chu[i]==0) ++chu0;
}
printf("%d\n%d\n",ru0,max(ru0,chu0));
return 0;
}