题面
1515
一句话题意：一个有向图，求有多少个入度为0的点，以及加多少条边可以使入度为0的点为0。
思路
先是Tarjin缩点，重新建图，然后求入度、出度为0的点，进行分析得到答案。
Tarjin的代码如下，就是基础，没有别的附加的
void tarjin(int k)
{
low[k]=dfn[k]=++cntt,st.push(k);
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);
if(low[k]==dfn[k])
{
co[k]=++num;
while(st.top()!=k) co[st.top()]=num,st.pop();
st.pop();
}
}//tarjin合点
然后是缩点重构图，直接算入度、出度
void rebuild()
{
for(int i=1; i<=n; i++)
for(int j=head[i]; j; j=a[j].nxt)
if(co[i]!=co[a[j].to]) in[co[a[j].to]]++,out[co[i]]++;
}
最后统计入度、出度为0的点进行分析
首先第一个答案肯定是tot1（入度为0的点的个数）
然后是第二个答案，是max(tot1,tot2)，因为你需要把这些强连通分量串成一个环，那么所有出度为0的点必须有边连出去，入度为0的点必须有边连进来，除非是只有一个强连通分量。
所以这一段代码就出来了
for(int i=1; i<=num; i++)
{
if(!in[i]) tot1++;
if(!out[i]) tot2++;
}
if(num==1) printf("1\n0\n");
else printf("%d\n%d\n",tot1,max(tot1,tot2));
代码
这一定是本文的“重点”
直接上代码
#include <bits/stdc++.h>
using namespace std;
int n,x;
int tot1,tot2,in[105],out[105];
int dfn[105],low[105],co[105],num,cntt;
int head[105],cnt;
struct node
{
int nxt,to;
} a[10005];
stack<int> st;
void add(int x,int y)
{
a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
void tarjin(int k)
{
low[k]=dfn[k]=++cntt,st.push(k);
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to]) tarjin(a[i].to),low[k]=min(low[k],low[a[i].to]);
else if(!co[a[i].to]) low[k]=min(low[k],dfn[a[i].to]);
if(low[k]==dfn[k])
{
co[k]=++num;
while(st.top()!=k) co[st.top()]=num,st.pop();
st.pop();
}
}//tarjin合点
void rebuild()
{
for(int i=1; i<=n; i++)
for(int j=head[i]; j; j=a[j].nxt)
if(co[i]!=co[a[j].to]) in[co[a[j].to]]++,out[co[i]]++;
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&x);
while(x!=0) add(i,x),scanf("%d",&x);
}
for(int i=1; i<=n; i++) if(!dfn[i]) tarjin(i);
rebuild();
for(int i=1; i<=num; i++)
{
if(!in[i]) tot1++;
if(!out[i]) tot2++;
}
if(num==1) printf("1\n0\n");
else printf("%d\n%d\n",tot1,max(tot1,tot2));
return 0;
}
小结
就是基础的Tarjin加上简单的分析，不多说，欢迎私信。
完结撒花！！！
别忘了点赞，关注，谢谢！！
