Cod sursa(job #1179145)

Utilizator vld7Campeanu Vlad vld7 Data 28 aprilie 2014 03:05:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
 
using namespace std;
 
ifstream f("ctc.in");
ofstream g("ctc.out");
 
const int MAX_N = 100005;
const int MAX_M = 200005;
 
int n, m;
int idx[MAX_N];         // indicele in parcurgere
int lowlink[MAX_N];     // cat de sus pot sa ma duc
int index;
 
bool inStack[MAX_N];
 
vector <int> L[MAX_N];
vector <vector <int> > Ans;
stack <int> Stack;
 
void init() {
    for (int i = 0; i < MAX_N; i++)
        idx[i] = -1;
}
 
void read() {
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        f >> a >> b;
        L[a].push_back (b);
    }
}
 
void tarjan (int nod) {
    index++;
    idx[nod] = index;
    lowlink[nod] = index;
    Stack.push (nod);
    inStack[nod] = true;
     
    for (vector <int> :: iterator it = L[nod].begin(); it != L[nod].end(); ++it)
        if (idx[*it] == -1) {
            tarjan (*it);
            lowlink[nod] = min (lowlink[nod], lowlink[*it]);
        } else if (inStack[*it]) {
            lowlink[nod] = min (lowlink[nod], idx[*it]);
        }
         
    // daca e radacina componentei tare conexe
    if (lowlink[nod] == idx[nod]) {
        vector <int> Temp;
        int temp_node;
         
        do {
            temp_node = Stack.top();
            Temp.push_back (temp_node);
            Stack.pop();
            inStack[temp_node] = false;
        } while (temp_node != nod);
         
        Ans.push_back (Temp);
    }
}
 
void write() {
    g << Ans.size() << '\n';
    for (int i = 0; i < (int)Ans.size(); i++) {
        for (vector <int> :: iterator it = Ans[i].begin(); it != Ans[i].end(); ++it)
            g << *it << " ";
        g << '\n';
    }
}
 
int main() {
    init();
    read();
     
    for (int i = 1; i <= n; i++)
        if (idx[i] == -1)
            tarjan (i);
         
    write();
         
    return 0;
}