Cod sursa(job #2734015)

Utilizator drknss_Hehe hehe drknss_ Data 31 martie 2021 11:41:37
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long LL;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#define int long long

#define cin in
#define cout out

ifstream in("ctc.in");
ofstream out("ctc.out");



const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const LL inf = 2e9;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 2e6 + 11;
const LL INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

int n, m, k, x, a[N], viz[N];

vector<int> v[N], vi[N], s, ctc[N];

void dfs(int nod){
    viz[nod] = 1;
    for(auto it : v[nod]){
        if(viz[it])continue;
        dfs(it);
    }
    s.pb(nod);
}

void dfs2(int nod, int c){
    ctc[c].pb(nod);
    viz[nod] = 0;
    for(auto it : vi[nod]){
        if(!viz[it])continue;
        dfs2(it, c);
    }
}

void solve() {

	cin >> n >> m;

	for(int i = 1, x, y; i <= m; i++){
        cin >> x >> y;
        v[x].pb(y);
        vi[y].pb(x);
	}

	for(int i = 1; i <= n; i++){
        if(!viz[i])dfs(i);
	}

    reverse(all(s));

	int C = 0;
	for(auto it : s){
        if(!viz[it])continue;
        dfs2(it, ++C);
	}


	cout << C << '\n';
	for(int i = 1; i <= C; i++){
        for(auto it : ctc[i]){
            cout << it << ' ';
        }cout << '\n';
	}

}

int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}