AcWing 367. 学校网络
原题链接
中等
作者:
eMAY
,
2019-10-29 21:53:18
,
所有人可见
,
阅读 1091
C++ 代码
QAQtarjan模板题呢,
首先缩点得到很多DAG,
对于第一问如果入度为零,那么给他一个就可以满足所有和它连接的东西
对于第二问显然我们不能满足条件是因为存在入度和出度为零的点,那么可以让每一对这样的点连起来,然后多出来的再自己随便搞一下,所以取max即可
另外只有一张图就不需要统计出度为零的点了,因为只有一个连通块啊,自己画图很好理解的
#include<bits/stdc++.h>
using namespace std;
#define maxn 5000009
int nxt[maxn],to[maxn],head[maxn],in[maxn],out[maxn];
int dfn[maxn],low[maxn],size[maxn],col[maxn];
bool vis[maxn];
int n,color,tot,cnt,m;
stack<int> s;
void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void tarjan(int u){
dfn[u]=low[u]=++tot;
vis[u]=1;
s.push(u);
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
color++;
int k;col[u]=color;
do{
k=s.top();s.pop();
col[k]=color;
vis[k]=0;
}while(k!=u);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
while(x!=0){
add(i,x);
scanf("%d",&x);
}
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(col[u]!=col[v]){
out[col[u]]++;
in[col[v]]++;
}
}
}
int ans1=0;int ans2=0;
for(int i=1;i<=color;i++){
if(in[i]==0) ans1++;
if(out[i]==0) ans2++;
}
if(color==1){
printf("1\n0");
return 0;
}
printf("%d\n%d",ans1,max(ans1,ans2));
return 0;
}