Cod sursa(job #1360475)

Utilizator somuBanil Ardej somu Data 25 februarie 2015 15:18:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define nmax 100005

using namespace std;

int n, m, nrComp = 0;
bool viz[nmax];
stack <int> S;
vector <int> G[nmax], Gt[nmax], comp[nmax];

void dfs(int nod) {
    viz[nod] = 1;
    for (int i = 0; i < G[nod].size(); i++)
        if (!viz[G[nod][i]])
            dfs(G[nod][i]);
    S.push(nod);
}

void k(int nod) {
    viz[nod] = true;
    comp[nrComp].push_back(nod);
    for (int i = 0; i < Gt[nod].size(); i++)
        if (!viz[Gt[nod][i]])
            k(Gt[nod][i]);
}

int main () {
    
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }
    
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);
    
    memset(viz, 0, sizeof(viz));
    for (; S.size();) {
        if (!viz[S.top()]) {
            nrComp++;
            k(S.top());
        }
        S.pop();
    }
    
    fout << nrComp << "\n";
    
    for (int i = 1; i <= nrComp; i++) {
        for (int j = 0; j < comp[i].size(); j++)
            fout << comp[i][j] << " ";
        fout << "\n";
    }
    
    fin.close();
    fout.close();
    
    return 0;
}