Cod sursa(job #1346080)

Utilizator dianaa21Diana Pislaru dianaa21 Data 18 februarie 2015 00:24:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
//Kosaraju
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100001
using namespace std;
ifstream is ("ctc.in");
ofstream os ("ctc.out");

vector <int> V[nmax], Vi[nmax], ANSW[nmax];
stack <int> S;
int N, M, Count, Found[nmax];
bool Vis[nmax];

void Read();
void DFS1(int);
void DFS2(int);

int main()
{
    Read();
    for(int i = 1; i <= N; ++i)
        if(!Vis[i]) DFS1(i);

    int node;
    while(!S.empty())
    {
        node = S.top();
        S.pop();
        if(!Found[node])
        {
            Count++;
            DFS2(node);
        }
    }
    for(int i = 1; i <= N; ++i)
        ANSW[Found[i]].push_back(i);

    vector<int>::iterator it;
    os << Count << "\n";
    for(int i = 1; i <= Count; ++i)
    {
        for(it = ANSW[i].begin(); it != ANSW[i].end(); ++it)
            os << *it << " ";
        os << "\n";
    }


    is.close();
    os.close();
    return 0;
}
void Read()
{
    int x, y;
    is >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        is >> x >> y;
        V[x].push_back(y);
        Vi[y].push_back(x);
    }
}
void DFS1(int node)
{
    vector <int> ::iterator it;
    Vis[node] = true;
    for(it = V[node].begin(); it != V[node].end(); ++it)
    {
        if(!Vis[*it])
            DFS1(*it);
    }
    S.push(node);
}
void DFS2(int node)
{
    vector <int> ::iterator it;
    Found[node] = Count;
    for(it = Vi[node].begin(); it != Vi[node].end(); ++it)
    {
        if(!Found[*it])
            DFS2(*it);
    }
}