Cod sursa(job #998927)

Utilizator 2dorTudor Ciurca 2dor Data 18 septembrie 2013 19:25:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

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

const int MAXN = 100005;
int indxx, n, m, x, y;

struct graph {
    vector <int> vecini;
    int index;
    int lowlink;
    bool in_stack;
}nodes[MAXN];

stack <int> stiva;

vector <vector <int> > multimea_componentelor;
vector <int> componenta;

void read() {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y;
        nodes[x].vecini.push_back(y);
    }
}

void tarjan(int nod) {
    nodes[nod].index = nodes[nod].lowlink = indxx++;//notam la ce index suntem
    stiva.push(nod); nodes[nod].in_stack = true;//bagam in stiva nodul
    vector <int>::iterator it;
    for (it = nodes[nod].vecini.begin(); it != nodes[nod].vecini.end(); ++it) {
        if (nodes[*it].index == -1) {//nod nevizitat
            tarjan(*it);
            nodes[nod].lowlink = min(nodes[nod].lowlink, nodes[*it].lowlink);
        }else if (nodes[*it].in_stack)//daca am mai vizitat nodul, verificam daca acesta se afla inca in stiva
            nodes[nod].lowlink = min(nodes[nod].lowlink, nodes[*it].lowlink);
    }
    if (nodes[nod].index == nodes[nod].lowlink) {//daca nodul node este radacina
        componenta.clear();
        int naux;
        do {
            naux = stiva.top();
            stiva.pop();
            componenta.push_back(naux);
            nodes[naux].in_stack = false;//am scos din stiva nodul naux
        }while (nod != naux);
        multimea_componentelor.push_back(componenta);
    }
}

void write() {
    fout << multimea_componentelor.size() << '\n';
    for (unsigned int i = 0; i < multimea_componentelor.size(); ++i) {
        for (unsigned int j = 0; j < multimea_componentelor[i].size(); ++j)
            fout << multimea_componentelor[i][j] << ' ';
        fout << '\n';
    }
}

int main() {
    read();
    for (int i = 1; i <= n; ++i)
        nodes[i].index = -1;
    for (int i = 1; i <= n; ++i)
        if (nodes[i].index == -1)//daca nodul i nu a mai fost vizitat, apelam tarjan()
            tarjan(i);
    write();
    fin.close();
    fout.close();
    return 0;
}