Cod sursa(job #948534)

Utilizator xbogdanBogdan Boamfa xbogdan Data 10 mai 2013 20:24:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 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;
}