96分气死人
查看原帖
96分气死人
195388
alvis楼主2021/6/18 20:57

有没有巨佬帮忙康康代码

第6个点死活过不去(应该输出1,我输出9)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4, M = 5 *(1e4);
int n, m, idx, times, cnt, tot, top;
struct node{
    int e, ne;
}g[M << 1];
int h[N], dfn[N], low[N];
int stk[N], out[N], id[N], num[N];
bool can[N];

void add(int a, int b){
    g[idx].e = b;
    g[idx].ne = h[a];
    h[a] = idx ++;
}
//tarjan模板
void tarjan(int u){
//    cout << u << endl;
    dfn[u] = low[u] = ++times;
    stk[++ top] = u, can[u] = true;
    
    for(int i = h[u];i != -1;i = g[i].ne){
        int j = g[i].e;
        if(!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(can[j]) low[u] = min(low[u], dfn[j]);
    }
    
    if(low[u] == dfn[u]){
        ++ cnt;
        while(stk[top + 1] != u){
            can[stk[top]] = false;
            id[stk[top]] = cnt;
				//存储当前缩的点的个数
            num[cnt] ++; 
            top --;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a, b;
    for(int i = 1;i <= m;i ++){
        cin >> a >> b;
        add(a, b);
    }
    
    for(int i = 1;i <= n;i ++){
        if(!dfn[i]) tarjan(i);
    }
    idx = 0;
    
    for(int i = 1;i <= n;i ++){
        for(int j = h[i];j != -1;j = g[j].ne) if(id[i] != id[g[j].e]) out[id[i]] ++;
    }
    
    bool flag = true;
    int res = 0;
    for(int i = 1;i <= cnt;i ++){
        if(out[i] == 0){
            //如果有两个出边为0的点
            if(!flag){
                cout << 0;
                return 0;
            }
            flag = false;
            res = num[i];
        }
    }
    cout << res;
    return 0;
}
2021/6/18 20:57
加载中...