校园网--tarjan求缩点的两个经典问题

1.入度为0点通知全部

2.DAG变SCC，别忘了特判称环的情况

P2746 [USACO5.3] 校园网Network of Schools - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n;
vector<int> mp[105],p[105];
int cnt,c; 
int low[105],dfn[105],sd[105];
stack<int> st;
void tarjan(int i)///tarjan缩点，即将强连通分量看成一个点 
{low[i]=dfn[i]=++cnt;st.push(i);for(int v:mp[i]){if(!dfn[v]){tarjan(v);low[i]=min(low[i],low[v]);}elseif(!sd[v]) low[i]=min(low[i],dfn[v]);}if(low[i]==dfn[i]){sd[i]=++c;while(st.top()!=i){sd[st.top()]=c;st.pop();}st.pop();}
}
int in[105],nn,ou[105];
int cc,mm;
int main() {ios::sync_with_stdio(0);cin.tie(0);//cout.tie(0);cin>>n;for(int i=1;i<=n;i++){int x;while(cin>>x&&x){mp[i].push_back(x);}}for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}for(int i=1;i<=n;i++){for(int v:mp[i]){if(sd[i]!=sd[v]){p[sd[i]].push_back(sd[v]);in[sd[v]]++;ou[sd[i]]++;}}}if(c==1)///特判成环的情况{cout<<1<<"\n"<<0;	} else///问题1：刻录光盘/受欢迎的牛--入度为0点通知全部问题 ///问题2：正常DAG（有向无环图）变SCC（强连通分图）///max{in为0的点个数与out度为0的个数 }{for(int i=1;i<=c;i++){if(!in[i]) nn++;if(!ou[i]) mm++;}cout<<nn<<endl;cout<<max(nn,mm);}return 0;
}