洛谷 2746 POJ 1236 SSL 1920 [USACO5.3] 校园网 Network of Schools#tarjan#

本文主要是介绍洛谷 2746 POJ 1236 SSL 1920 [USACO5.3] 校园网 Network of Schools#tarjan#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目以及kosaraju的做法

---

分析

这里采用tarjan的方法，具体详见受欢迎的牛

---

代码

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
struct node{int x,y,next;}e[3001]; stack<int>uk; bool v[101]; int ind[101];
int inn,ans,ls[101],n,tot,m,in[101],out[101],oun,low[101],dfn[101]; 
void add(int x,int y){e[++m].x=x; e[m].y=y; e[m].next=ls[e[m].x]; ls[e[m].x]=m;}
void tarjan(int x){dfn[x]=low[x]=++tot; uk.push(x); v[x]=1;int t=ls[x];while (t){if (!dfn[e[t].y]){tarjan(e[t].y);low[x]=min(low[x],low[e[t].y]);}else if (v[e[t].y]&&low[x]>dfn[e[t].y]) low[x]=dfn[e[t].y];t=e[t].next;}if (low[x]==dfn[x]){ans++; int k;do{k=uk.top();ind[k]=ans;v[k]=0;uk.pop();}while (k!=x);}
}
int main(){scanf("%d",&n);for (int i=1;i<=n;i++){int k=i;while (scanf("%d",&k)&&k) add(i,k);}for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);if (ans==1) printf("1\n0");else{for (int i=1;i<=m;i++)if (ind[e[i].x]!=ind[e[i].y]) in[ind[e[i].y]]++,out[ind[e[i].x]]++;for (int i=1;i<=ans;i++) inn+=(!in[i]),oun+=(!out[i]);printf("%d\n%d",inn,max(inn,oun));}return 0;
}

这篇关于洛谷 2746 POJ 1236 SSL 1920 [USACO5.3] 校园网 Network of Schools#tarjan#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---