Cod sursa(job #2073470)

Utilizator giotoPopescu Ioan gioto Data 23 noiembrie 2017 10:55:13
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;

int Sol, n, m, NR;
int d[100005], st[100005];
vector <int> v[100005];
vector <int> ctc[100005];
bool f[100005];
inline void dfs(int nod, int k){
    f[nod] = 1; d[nod] = k;
    st[NR++] = nod;
    for(auto it : v[nod]){
        if(d[it] == 0){
            dfs(it, k + 1);
            d[nod] = min(d[it], d[nod]);
        }
        else if(f[it]) d[nod] = min(d[nod], d[it]);
    }
    if(d[nod] == k){
        int x = nod;
        ++Sol;
        do{
            x = st[--NR];
            f[x] = 0;
            ctc[Sol].push_back(x);

        }while(x != nod);
    }

}
int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int x, y;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
    }
    for(int i = 1; i <= n ; ++i){
        if(d[i]) continue ;
        NR = 0; dfs(i, 1);
    }
    printf("%d\n", Sol);
    for(int i = 1; i <= Sol ; ++i){
        for(auto it : ctc[i])
            printf("%d ", it);
        printf("\n");
    }
    return 0;
}