Cod sursa(job #2121535)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 3 februarie 2018 20:02:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <cstring>
#include <vector>

#define maxn 100005

using namespace std;

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

int n, m, k, sol;
int used[maxn], v[maxn];
vector < int > G[maxn];
vector < int > GT[maxn];
vector < int > CTC[maxn];

void DFS(int u){
    used[u] = 1;
    for(int i = 0; i < G[u].size(); ++i){
        if(!used[G[u][i]]) DFS(G[u][i]);
    }
    v[k--] = u;
}

void DFST(int u){
    used[u] = 1;
    CTC[sol].push_back(u);
    for(int i = 0; i < GT[u].size(); ++i){
        if(!used[GT[u][i]]) DFST(GT[u][i]);
    }
}

int main()
{
    f >> n >> m;
    k = n;
    for(int i = 1; i <= m; ++i){
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i){
        if(!used[i]) DFS(i);
    }
    memset(used, 0, sizeof(used));

    for(int i = 1; i <= n; ++i){
        if(!used[v[i]]){
            ++sol;
            DFST(v[i]);
        }
    }

    g << sol << '\n';
    for(int i = 1; i <= sol; ++i){
        for(int j = 0; j < CTC[i].size(); ++j)
            g << CTC[i][j] << ' ';
        g << '\n';
    }

    return 0;
}