Cod sursa(job #1932566)

Utilizator valentin50517Vozian Valentin valentin50517 Data 19 martie 2017 21:38:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
#define pb push_back
#define maxn 100100
using namespace std;
int N,M,A[maxn],a,rs;
vector<int> V[maxn],IV[maxn],RS[maxn];
bool B[maxn];
void dfs(int x){
    if(B[x]) return; B[x]=1;
    for(auto it:V[x]) dfs(it);
    A[++a] = x;
}

void dfss(int x){
    if(!B[x]) return; B[x]=0;
    for(auto it:IV[x]) dfss(it);
    RS[rs].pb(x);
}

int main() {
	ifstream cin("ctc.in");
	ofstream cout("ctc.out");
    cin >> N >> M;
    for(int x,y;M--;){
        cin >> x >> y;
        V[x].pb(y);
        IV[y].pb(x);
    }
    for(int i = 1;i<=N;i++) dfs(i);
    for(int i = N;i;i--) if(B[A[i]]) ++rs,dfss(A[i]);
    cout << rs << '\n';
    while(rs){
        for(auto it:RS[rs]) cout << it << ' ';
        cout << '\n';
        rs--;
    }
}