Cod sursa(job #1112099)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 19 februarie 2014 13:46:12
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

#define foreach(i, v) for (vector<int>::iterator (i) = (v).begin(); (i) != (v).end(); ++(i))

int n, m, nctc = 0;
int s[100005];
vector<int> g[100005], tg[100005], ctc[100005];
bool tr[100005];

void topsort(int nod) {
    tr[nod] = true;
    foreach(i, g[nod])
        if (!tr[*i])
            topsort(*i);
    s[++s[0]] = nod;
}

void dfs(int nod) {
    tr[nod] = true;
    foreach(i, tg[nod])
        if (!tr[*i])
            dfs(*i);
    ctc[nctc].push_back(nod);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
		tg[y].push_back(x);
    }
    
    for (int i = 1; i <= n; ++i)
        if (!tr[i])
            topsort(i);
    
    for (int i = 1; i <= n; ++i)
        tr[i] = false;
    for (int i = n; i >= 1; --i)
        if (!tr[s[i]]) {
            ++nctc;
            dfs(s[i]);
        }
    
    fout << nctc << '\n';
	for (int i = 1; i <= nctc; ++i)
		sort(ctc[i].begin(), ctc[i].end());
    for (int i = 1; i <= nctc; ++i, fout << '\n')
        foreach(j, ctc[i])
            fout << *j << ' ';
    
    fin.close();
    fout.close();
}