Cod sursa(job #2029342)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 29 septembrie 2017 21:03:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,m,x,y,v[200005];

vector <int> g[200005],q,p,h[200005];

vector <vector<int>> ans;

void DFS(int nod){
    if(v[nod]) return;
    v[nod]=1;
    q.push_back(nod);
    for(int i : g[nod]) DFS(i);
}

void Ret(int nod){
    if(v[nod]!=1) return;
    v[nod]=2;
    p.push_back(nod);
    for(int i : h[nod]) Ret(i);

}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> x >> y;
        g[x].pb(y);
        h[y].pb(x);
    }
    for(int i=1;i<=n;i++){
        if(!v[i]){
            DFS(i);
            for(int j : q){
                if(v[j]!=2) Ret(j),ans.push_back(p),p.clear();
            }
            q.clear();
        }
    }
    cout << ans.size() << '\n';
    for(vector<int> i : ans){
        for(int j : i) cout << j << ' ';
        cout << '\n';
    }
}