Cod sursa(job #1601678)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 16 februarie 2016 10:18:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <vector>
#include <stack>
#include <list>
#define f first
#define s second
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, x, y, i, reach, nrComp;
bool onStack[100100];
vector<pair<int, int> > nodeOrders(100100);
vector<list<int> > graph(100100);
list<list<int> > solution;
list<int> xList;
stack<int> strongConnect;

void tareConex(int nod) {
    int aux;
    if (nodeOrders[nod].f == 0) {
        reach++;
        nodeOrders[nod].f = reach;
        nodeOrders[nod].s = reach;
        onStack[nod] = true;
        strongConnect.push(nod);

        for (list<int>::iterator it = graph[nod].begin() ; it != graph[nod].end() ; it++) {
            if (nodeOrders[*it].f == 0) {
                tareConex(*it);
                nodeOrders[nod].s = min(nodeOrders[nod].s, nodeOrders[*it].s);
            } else if (onStack[*it] == true) {
                nodeOrders[nod].s = min(nodeOrders[nod].s, nodeOrders[*it].s);
            }
        }

        if (nodeOrders[nod].f == nodeOrders[nod].s) {
            do {
                aux = strongConnect.top(); strongConnect.pop();
                onStack[aux] = false;
                xList.push_back(aux);
            } while (aux != nod);

            solution.push_back(xList);
            xList.clear();
            nrComp++;
        }
    }
}

int main()
{
    fin>>n>>m;
    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y;
        graph[x].push_back(y);
    }

    for (i = 1 ; i <= n ; i++) {
        tareConex(i);
    }

    fout<<nrComp;
    for (list<list<int> >::iterator listIt = solution.begin() ; listIt != solution.end() ; listIt++) {
        fout<<'\n';
        for (list<int>::iterator it = listIt->begin() ; it != listIt->end() ; it++) {
            fout<<*it<<' ';
        }
    }

return 0;
}