Cod sursa(job #1004455)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 2 octombrie 2013 19:08:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

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

struct node {
    bool vizitat;
    int mini;
    int grad;
    vector<int> vecini;
};

struct cuplu {
    int a;
    int b;
};

int n, m, i, ii, a, b, s1, s2, k = 1;
node nodes[100001];
stack<int> stiva;
vector<int> sol;
vector<vector<int> > solutie;
bool v[100001];

void dfs(int x) {
    int j;
    int l = nodes[x].vecini.size();
    for(j = 0; j < l; j++) {
        int vecin = nodes[x].vecini[j];
        //cout << "nod: " << x << '(' << nodes[x].mini << ')' << "-vecin: " << vecin << '(' << nodes[vecin].mini << ")\n";
        if(nodes[vecin].vizitat == false) {
            stiva.push(vecin);
            v[vecin] = true;
            nodes[vecin].vizitat = true;
            nodes[vecin].grad = nodes[vecin].mini = ++k;
            dfs(vecin);
            nodes[x].mini = min(nodes[x].mini, nodes[vecin].mini);
            //cout << "nod: "<< x << '(' << nodes[x].mini << ")-vecin: " << vecin << '(' << nodes[vecin].mini << ")\n";
        }
        else {
            if(v[vecin] == true) {
                nodes[x].mini = min(nodes[x].mini, nodes[vecin].mini);
                //cout << "nod': " << x << '(' << nodes[x].mini << ")\n";
            }
        }
    }
    if(nodes[x].grad == nodes[x].mini) {
        while(stiva.top() != x) {
            sol.push_back(stiva.top());
            v[stiva.top()] = false;
            stiva.pop();
        }
        sol.push_back(stiva.top());
        v[stiva.top()] = false;
        stiva.pop();
        solutie.push_back(sol);
        sol.clear();
    }
}

int main() {
    fin >> n >> m;
    for(i = 0; i < m; i++) {
        fin >> a >> b;
        nodes[a].vecini.push_back(b);
    }
    for(i = 1; i <= n; i++) {
        if(nodes[i].vizitat == false) {
            nodes[i].grad = k;
            nodes[i].mini = k;
            stiva.push(i);
            v[i] = true;
            nodes[i].vizitat = true;
            dfs(i);
        }
    }
    s1 = solutie.size();
    fout << s1 << '\n';
    for(i = s1 - 1; i >= 0; i--) {
        sol = solutie[i];
        s2 = sol.size();
        for(ii = s2 - 1; ii >= 0; ii--) {
            fout << sol[ii] << ' ';
        }
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}