Cod sursa(job #2964372)

Utilizator tiberia_farkasFarkas Tiberia tiberia_farkas Data 12 ianuarie 2023 21:05:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int> > g, gt, t;
vector<bool> v;
vector<int> s;

int n, m;

void dfs(int k) {
    v[k] = 1;
    for ( auto x : g[k] ) {
        if ( !v[x] ) dfs(x);
    }
    s.push_back(k);
}

void dfs1(int k, int ct) {
    v[k] = 1;
    for ( auto x : gt[k] ) {
        if ( !v[x] ) dfs1(x, ct);
    }
    t[ct].push_back(k);
}


int main()
{
    int i, x, y, cnt = 0;
    fin >> n >> m;
    g = gt = vector<vector<int> > ( n + 1 );
    for ( i = 1; i <= m; ++i ) {
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    v = vector<bool> (n+1, 0);
    for ( i = 1; i <= n; ++i ) {
        if ( !v[i] ) dfs(i);
    }
    v = vector<bool> (n+1, 0);
    t = vector<vector<int> > ( n + 1 );
    for ( i = s.size() - 1; i >= 0; --i ) {
        if ( !v[s[i]] ) {
            cnt++;
            dfs1(s[i], cnt);
        }
    }
    fout << cnt << '\n';
    for ( i = 1; i <= cnt; ++i ) {
        for ( auto x : t[i] ) fout << x << " ";
        fout << '\n';
    }

    return 0;
}