题目传送门 https://www.luogu.org/problem/P2341
解题思路:
先求强联通分量, 缩点, 然后统计新图中有几个点出度为 0, 如果大于 1 个, 则说明这不是一个连通图, 答案即为 0. 否则入度为 0 的那个强连通分量的点数即为答案
AC 代码:
- #include<iostream>
- #include<cstdio>
- #include<stack>
- #include<set>
- using namespace std;
- int daan,n,m,head[10001],tot;
- int dfn[10001],low[10001],sum,rp;
- int belong[10001],_head[10001],num[10001];
- bool vis[10001];
- struct kk{
- int to,next;
- }e[50001],a[50001];
- stack<int> s;
- set<int> ans[10001];
- inline void add(int x,int y) {
- e[++tot].to = y;
- e[tot].next = head[x];
- head[x] = tot;
- }
- inline void tarjan(int x) {
- dfn[x] = low[x] = ++sum;
- int v;
- s.push(x);
- vis[x] = 1;
- for(int i = head[x];i != 0; i = e[i].next) {
- v = e[i].to;
- if(!dfn[v]) {
- tarjan(v);
- low[x] = min(low[x],low[v]);
- }
- else if(vis[x])
- low[x] = min(low[x],dfn[v]);
- }
- if(dfn[x] == low[x]) {
- rp++;
- do {
- v = s.top();
- s.pop();
- belong[v] = rp;
- num[rp]++;
- vis[x] = false;
- }
- while(v != x);
- }
- }
- inline void _add(int x,int y) {
- a[++tot].to = y;
- a[tot].next = _head[x];
- _head[x] = tot;
- }
- inline void findin() {
- for(int i = 1;i <= rp; i++)
- for(int j = _head[i];j != 0; j = a[j].next) {
- int o = a[j].to;
- ans[i].insert(o);
- }
- }
- int main() {
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= m; i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- add(x,y);
- }
- for(int i = 1;i <= n; i++)
- if(!dfn[i]) // 求强连通分量
- tarjan(i);
- tot = 0;
- for(int i = 1;i <= n; i++)// 构建新图, 其实没啥必要
- for(int j = head[i];j != 0; j = e[j].next)
- if(belong[i] != belong[e[j].to])
- _add(belong[i],belong[e[j].to]);
- findin();
- for(int i = 1;i <= rp; i++)// 找入度为 0 的点
- if(ans[i].size() == 0) {
- if(daan != 0) {
- printf("0");
- return 0;
- }
- daan = i;
- }
- printf("%d",num[daan]);
- return 0;
- }
第一次的做法, 用了 set, 较麻烦
- #include<iostream>
- #include<cstdio>
- #include<stack>
- #include<set>
- using namespace std;
- int daan,n,m,head[10001],tot;
- int _out[10001],dfn[10001],low[10001];
- int sum,rp,belong[10001];
- int _head[10001],num[10001];
- bool vis[10001];
- struct kk{
- int to,next;
- }e[50001],a[50001];
- stack<int> s;
- inline void add(int x,int y) {
- e[++tot].to = y;
- e[tot].next = head[x];
- head[x] = tot;
- }
- inline void tarjan(int x) {
- dfn[x] = low[x] = ++sum;
- int v;
- s.push(x);
- vis[x] = 1;
- for(int i = head[x];i != 0; i = e[i].next) {
- v = e[i].to;
- if(!dfn[v]) {
- tarjan(v);
- low[x] = min(low[x],low[v]);
- }
- else if(vis[x])
- low[x] = min(low[x],dfn[v]);
- }
- if(dfn[x] == low[x]) {
- rp++;
- do {
- v = s.top();
- s.pop();
- belong[v] = rp;
- num[rp]++;
- vis[x] = false;
- }
- while(v != x);
- }
- }
- inline void _add(int x,int y) {
- a[++tot].to = y;
- a[tot].next = _head[x];
- _head[x] = tot;
- }
- int main() {
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= m; i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- add(x,y);
- }
- for(int i = 1;i <= n; i++)
- if(!dfn[i])
- tarjan(i);
- tot = 0;
- for(int i = 1;i <= n; i++)
- for(int j = head[i];j != 0; j = e[j].next)
- if(belong[i] != belong[e[j].to])
- _out[belong[i]]++;
- for(int i = 1;i <= rp; i++)
- if(_out[i] == 0) {
- if(daan != 0) {
- printf("0");
- return 0;
- }
- daan = i;
- }
- printf("%d",num[daan]);
- return 0;
- }
改进后的代码, 发现不用 set, 比较精简
来源: http://www.bubuko.com/infodetail-3285448.html