Cod sursa(job #1168110)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 6 aprilie 2014 22:32:34
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<cstdio>
#include<vector>
#include<deque>
#include<bitset>

using namespace std;

const int NMAX = 100000+5;

void Read(),Kosaraju(),Print();

int N,M,Nr_CTC;
vector<int> Graph[NMAX];
vector<int> Transpose_Graph[NMAX];
vector<int> CTC[NMAX];
deque<int> SortareT;
bitset<NMAX> Viz;

void DFS(int nod)
{
    vector<int>::iterator it;

    Viz[nod] = 1;

    for(it = Graph[nod].begin(); it != Graph[nod].end(); it++)
        if(!Viz[*it]) DFS(*it);

    SortareT.push_front(nod);
}

void DFS_Transpose(int nod)
{
    vector<int>::iterator it;

    Viz[nod] = 1;

    CTC[Nr_CTC].push_back(nod);

    for(it = Transpose_Graph[nod].begin(); it != Transpose_Graph[nod].end(); it++)
        if(!Viz[*it]) DFS_Transpose(*it);
}

int main()
{
    Read();
    Kosaraju();
    Print();

    return 0;
}

void Read()
{
    int x,y;

    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    scanf("%d%d",&N,&M);

    for(; M; --M)
    {
        scanf("%d%d",&x,&y);
        Graph[x].push_back(y);
        Transpose_Graph[y].push_back(x);
    }
}

void Kosaraju()
{
    int i;

    for(i = 1; i <= N; i++)
        if(!Viz[i]) DFS(i);

    Viz = 0;

    for(i = 1; i <= N; i++)
        if(!Viz[i])
        {
            Nr_CTC++;
            DFS_Transpose(i);
        }
}

void Print()
{
    int i;
    vector<int>::iterator it;

    printf("%d\n",Nr_CTC);

    for(i = 1; i <= Nr_CTC; i++)
    {
        for(it = CTC[i].begin(); it != CTC[i].end(); it++)
            printf("%d ",*it);
        printf("\n");
    }
}