题目描述

约翰的N(2≤N≤10000)只奶牛非常兴奋,因为这是舞会之夜!她们穿上礼服和新鞋子,别上鲜花,她们要表演圆舞.

只有奶牛才能表演这种圆舞.圆舞需要一些绳索和一个圆形的水池.奶牛们围在池边站好,顺时针顺序由1到N编号.每只奶牛都面对水池,这样她就能看到其他的每一只奶牛.为了跳这种圆舞,她们找了M(2≤M≤50000)条绳索.若干只奶牛的蹄上握着绳索的一端,绳索沿顺时针方绕过水池,另一端则捆在另一些奶牛身上.这样,一些奶牛就可以牵引另一些奶牛.有的奶牛可能握有很多绳索,也有的奶牛可能一条绳索都没有对于一只奶牛,比如说贝茜,她的圆舞跳得是否成功,可以这样检验:沿着她牵引的绳索,找到她牵引的奶牛,再沿着这只奶牛牵引的绳索,又找到一只被牵引的奶牛,如此下去,若最终能回到贝茜,则她的圆舞跳得成功,因为这一个环上的奶牛可以逆时针牵引而跳起旋转的圜舞.如果这样的检验无法完成,那她的圆舞是不成功的.

如果两只成功跳圆舞的奶牛有绳索相连,那她们可以同属一个组合.
给出每一条绳索的描述,请找出,成功跳了圆舞的奶牛有多少个组合?

人话题意

一个子图中任意两头牛都可以互相到达。
求出这样的子图的个数。
(这不就是强连通分量的裸题吗?)

输入

第1行输入N和M,接下来M行每行两个整数A和B,表示A牵引着B.

输出

成功跳圆舞的奶牛组合数.

样例输入

5 4
2 4
3 5
1 2
4 1

样例输出

1

提示

1,2,4 这三只奶牛同属一个成功跳了圆舞的组合.而3,5两只奶牛没有跳成功的圆舞

来源

Silver

题解

使用 Tarjon 求强连通分量个数即可,模板题

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5e4 + 1;
 
int n, m;
int head[N], nex[N], to[N], ce;
void add(int u, int v) {
    to[++ce] = v;
    nex[ce] = head[u];
    head[u] = ce;
}
 
int dfn[N], low[N], num[N], used[N], stamp, re;
int stk[N], idx;
 
void tarjan(int x) {
    dfn[x] = low[x] = ++stamp;
    stk[++idx] = x;
    used[x] = true;
    for(int i=head[x]; i!=-1; i=nex[i]) {
        int v = to[i];
        if(!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if(used[v]) {
            low[x] = min(low[x], dfn[v]);
        }
    }
    if(low[x] == dfn[x]) {
        re++;
        do {
            int e = stk[idx];
            num[re]++;
            used[e] = false;
            idx--;
        } while(x != stk[idx + 1]);
    }
}
 
int main() {
    memset(head, -1, sizeof head);
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        add(u, v);
    }
    for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
 
    int ans = 0;
    for(int i=1; i<=re; i++) {
        if(num[i] >= 2) ans ++;
    }
 
    printf("%d\n", ans);
     
    return 0;
}