kuangbin专题-连通图A - Network of Schools
这道题的意思是就是
问题
1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
2：至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。
其实问题1就是问，这个图的支配集有多少？？？解决这个问题非常简单，把图缩点后，找到有多少个入度为0的点，就是支配集。一个支配内，所有点可能不是强连通的，但是都可以通过这个点到达。
而问题二其实更加简单，我们只需要把入读为0的点和出度为0的点的数目取一个最大值即可，至于问什么，很简单，我们可以把出度为0的点连接到入度为0的点上面去，这样就保证图的强连通性质。其实这就是求一个图的补图。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int N = 100010,M=1000010; int ver[M],Next[M],head[N],dfn[N],low[N]; int sta[N],ins[N],c[N],in_deg[N],out_deg[N]; int n,m,tot,num,top,cnt; void add(int x,int y) { ver[++tot]=y,Next[tot]=head[x],head[x]=tot; } void tarjan(int x) { dfn[x]=low[x]=++num;//序列号+1 sta[++top]=x,ins[x]=1;//入栈，并标记在栈内 for (int i=head[x]; i; i=Next[i]) //开始访问 if(!dfn[ver[i]]) //如果没有被处理过 { tarjan(ver[i]);//DFS low[x]=min(low[x],low[ver[i]]); //递归出来，比较谁是谁的儿子／父亲，就是树的对应关系，涉及到强连通分量子树最小根的事情 } else if (ins[ver[i]]) low[x]=min(low[x],dfn[ver[i]]); //比较谁是谁的儿子／父亲。就是链接对应关系 if (dfn[x] == low[x])//发现是整个强连通分量的子树里面的最小根。 { cnt++; int y; do { y=sta[top--],ins[y]=0; c[y]=cnt; //scc[cnt].push_back(y); } while(x!=y); } } void solve(int n) { for (int i=1; i<=n; i++) { if (!dfn[i]) { tarjan(i); } } if (cnt==1) { printf("1\n0\n"); return; } for (int u=1; u<=n; ++u) { for (int j=head[u]; j; j=Next[j]) { int v=ver[j]; if (c[u]==c[v]) { continue; } out_deg[c[u]]++; in_deg[c[v]]++; } } int a,b; a=0; b=0; for (int i=1; i<=cnt; i++) { if (in_deg[i]==0) { a++; } else if (out_deg[i]==0) { b++; } } printf("%d\n",a); printf("%d\n",max(a,b)); } void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(head,0,sizeof(head)); memset(in_deg,0,sizeof(in_deg)); memset(out_deg,0,sizeof(out_deg)); memset(ins,0,sizeof(ins)); top=0; tot=0; cnt=0; num=0; } int main() { int tmp; while(~scanf("%d",&n)) { init(); for (int i=1; i<=n; i++) { while(scanf("%d",&tmp)&&tmp) { add(i,tmp); } } solve(n); } return 0; }
