Cod sursa(job #2027572)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 26 septembrie 2017 12:55:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define MAX 100005
using namespace std;

int n, m, x, y;
vector<int> l[MAX], r[MAX];
stack<int> s;
bool viz[MAX], vizr[MAX];
vector<int> c;
vector<vector<int> > ctc;

void dfs(int x) {
    viz[x] = 1;
    for(int i = 0; i < l[x].size(); ++i)
        if(!viz[l[x][i]])
            dfs(l[x][i]);
    s.push(x);
}

void dfsr(int x) {
    c.push_back(x);
    vizr[x] = 1;
    for(int i = 0; i < r[x].size(); ++i)
        if(!vizr[r[x][i]])
            dfsr(r[x][i]);
}

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

    f >> n >> m;
    for(int i = 0; i < m; ++i) {
        f >> x >> y;
        l[x].push_back(y);
        r[y].push_back(x);
    }

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

    while(!s.empty()) {
        int x = s.top();
        s.pop();
        if(!vizr[x]) {
            dfsr(x);
            ctc.push_back(c);
            c.clear();
        }
    }

    g << ctc.size() << "\n";
    for(int i = 0; i < ctc.size(); ++i) {
        for(int j = 0; j < ctc[i].size(); ++j)
            g << ctc[i][j] << " ";
        g << "\n";
    }
    return 0;
}