Cod sursa(job #1091554)

Utilizator andreea_alexandraAndreea Alexandra andreea_alexandra Data 25 ianuarie 2014 20:11:28
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <cstdio>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int const N_MAX=100001;
//fstream fin("grader_test10.in", ios::in);
//fstream fout("grader_test10.out", ios::out);
vector <int> graph[N_MAX], graphT[N_MAX], comp[N_MAX], stock;
int   k=0;
bool vizitat[N_MAX];

int N, M;


void citire()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int x, y;
    scanf("%d", &N);
    scanf("%d", &M);
    for(int i=0; i<M; i++)
    {
        scanf("%d", &x);
        scanf("%d", &y);
        graph[x].push_back(y);
        graphT[y].push_back(x);
    }
}

void dfs1(int x)
{
    vizitat[x]=true;
    if(graphT[x].size() > 0)
    {
        //int start=*(graphT[x].begin());
        //int finish=*(graphT[x].end());
        //for(unsigned int i=0; i<graphT[x].size(); i++)
        for(vector<int>::iterator it=graphT[x].begin(); it!=graphT[x].end(); it++)
        {
            int current=*it;
            if(!vizitat[current])
                dfs1(current);
        }
    }
    stock.push_back(x);
}

void dfs2(int x)
{
    vizitat[x]=true;
    //for(unsigned int i=0; i<graph[x].size(); i++)
    if(graph[x].size() > 0)
    {
        for(vector<int>::iterator it=graph[x].begin(); it!=graph[x].end(); it++)
        {
            if(!vizitat[*it])
                dfs2(*it);
        }
    }
    comp[k].push_back(x);
}

void SortareTop()
{
    for(int i=1; i<=N; i++)
        if(!vizitat[i])
            dfs1(i);
}

int main()
{
    citire();
    SortareTop();
    memset(vizitat, false, sizeof(vizitat));
    for(vector<int>::reverse_iterator it=stock.rbegin(); it!=stock.rend(); it++)
    {
        if(!vizitat[*it])
        {
            k++;
            dfs2(*it);
        }
    }
    printf("&d\n", k);
    for(int i=1; i<=k; i++)
    {
        //for(unsigned int j=0; j<comp[i].size(); j++)
        for(vector<int>::iterator it=comp[i].begin(); it!=comp[i].end(); it++)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}