首页 > 其他 > 详细

[Luogu] 受欢迎的牛

时间:2018-01-14 11:44:15      阅读:20      评论:0      收藏:0      [点我收藏+]

标签:tle   opp   缩点   https   getchar()   node   ref   har   names   

https://www.luogu.org/problemnew/show/P2341

Tarjan 缩点 + 判断出度

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;

#define yxy getchar()

int Tarjan_tim, now = 1, n, m, topp, bel;
int Stack[N], head[N], dfn[N], low[N], belong[N], Cnt[N], Out[N];
struct Node {int u, v, nxt;} G[M];
bool vis[N];

inline int read(){
    int x = 0; char c = yxy;
    while(c < 0 || c > 9) c = yxy;
    while(c >= 0 && c <= 9) x = x * 10 + c - 0, c = yxy;
    return x;
}

inline void add(int u, int v){
    G[now].u = u; G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;
}

void Tarjan(int u){
    dfn[u] = low[u] = ++ Tarjan_tim;
    vis[u] = 1;
    Stack[++ topp] = u;
    for(int i = head[u]; ~ i; i = G[i].nxt){
        int v = G[i].v;
        if(!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], low[v]);
    }
    if(dfn[u] == low[u]){
        vis[u] = 0; belong[u] = ++ bel;
        while(Stack[topp] != u){
            vis[Stack[topp]] = 0;
            belong[Stack[topp]] = bel;
            topp --;
        }
        topp --;
    }
}


int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i ++) head[i] = -1;
    for(int i = 1; i <= m; i ++) {
        int u = read(); int v = read();
        add(u, v);
    }
    for(int i = 1; i <= n; i ++) if(!dfn[i]) Tarjan(i);    
    for(int u = 1; u <= n; u ++){
        for(int i = head[u]; ~ i; i = G[i].nxt){
            int v = G[i].v;
            if(belong[u] != belong[v]) Out[belong[u]] ++;
        }
        Cnt[belong[u]] ++;
    }
    int js = 0, Ans;
    for(int i = 1; i <= bel; i ++){
        if(!Out[i]) {js ++; Ans = Cnt[i];}
    }
    if(js != 1) cout << "0";
    else cout << Ans;
    return 0;
}

 

[Luogu] 受欢迎的牛

标签:tle   opp   缩点   https   getchar()   node   ref   har   names   

原文:https://www.cnblogs.com/shandongs1/p/8282400.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号