Cod sursa(job #948535)

Utilizator xbogdanBogdan Boamfa xbogdan Data 10 mai 2013 20:25:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include "iostream"
#include "fstream"
#include "vector"
#include "stack"
using namespace std;
 
#define NMAX 100005
 
ifstream inf("ctc.in");
ofstream outf("ctc.out");
 
int nr_nod;
bool vizitat[NMAX];
int count;
stack<int> S;
vector<int>  sol[NMAX], in[NMAX], out[NMAX];
 
void Read()
{
    int x, y, muchii;
    inf >> nr_nod >> muchii;
    for (int i = 0; i < muchii; ++ i)
    {
        inf >> x >> y;
        in[x].push_back(y);
        out[y].push_back(x);
    }
}
void Print()
{
    outf << count << '\n';
    vector <int> ::iterator it;
    for (int i = 1; i <= count; ++i)
    {
        for (it = sol[i].begin(); it != sol[i].end(); ++ it)
            outf << *it << " ";
        outf << '\n';
    }
}
void Dff(int start)
{
    vizitat[start] = true;
    vector <int>::iterator it;
    for (it = in[start].begin(); it != in[start].end(); ++it)
        if (vizitat[*it] == 0)
            Dff(*it);
   S.push(start);
}
void Dfs(int start)
{
    vizitat[start] = false;
    sol[count].push_back(start);
    vector <int>::iterator it;
    for (it = out[start].begin(); it != out[start].end(); ++ it)
        if (vizitat[*it] == true)
            Dfs(*it);
}
void Kosaraju()
{
    for (int i = 1; i <= nr_nod; ++ i)
        if (vizitat[i] == false)
            Dff(i);
 
    while (!S.empty()) {
        if (vizitat[S.top()] == true)
        {
            count ++;
            Dfs(S.top());
        }
        S.pop();
    }
}
int main()
{
    Read();
    Kosaraju();
    Print();
    return 0;
}