- 学校网络
- 2016-10-03 21:57:01 @
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
int head[500],tot,n,nextn[500],tov[500];
int vis[500],timen,dfn[500],low[500];
int indu[500],outdu[500],col,colorn[500],ans1,ans2,a,b;
vector<int>q;
void build()
{
cin>>n;
for (int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
while (x!=0)
{
tot++;
nextn[tot]=head[i];
head[i]=tot;
tov[tot]=x;
scanf("%d",&x);
}
}
}
void tarjan(int k)
{
vis[k]=1;
dfn[k]=low[k]=timen++;
q.push_back(k);
for (int i=head[k];i;i=nextn[i])
{
int v=tov[i];
if (vis[v]==0)
{
tarjan(v);
low[k]=min(low[k],low[v]);
}
else if (colorn[v]==0) low[k]=min(low[k],dfn[v]);
}
if (low[k]==dfn[k])
{
col++;
for (;;)
{
int x=q.back();
q.pop_back();
colorn[x]=col;
if (x==k) break;
}
}
}
int main()
{
//freopen("学校网络.in","r",stdin);
//freopen("学校网络.out","w",stdout);
build();
for (int i=1;i<=n;i++)
{
timen=1;
if (vis[i]==0)
tarjan(i);
}
for (int i=1;i<=col;i++) indu[i]=outdu[i]=1;
for (int i=1;i<=n;i++)
for (int j=head[i];j;j=nextn[j ])
if (colorn[tov[j]]!=colorn[i]) outdu[colorn[i]]=indu[colorn[tov[j]]]=0;
for (int i=1;i<=col;i++)
{
if (indu[i]==1) a++;
if (outdu[i]==1) b++;
}
ans1=a;
ans2=max(a,b);
if (col==1) {ans1=1;ans2=0;}
cout<<ans1<<endl<<ans2;
return 0;
}
2 条评论
-
lys710820 LV 8 @ 2016-10-04 08:00:38
谢谢啦~(≧▽≦)/~
-
2016-10-03 23:01:02@
- 本题题面并没有限定边数,因此最多可能有
\(O(n^2)\)
条边,你的数组开小了 - 最好看一下编辑框下方的"编辑器快速入门"来学习发布更漂亮的代码
- 本题题面并没有限定边数,因此最多可能有
- 1