Cod sursa(job #1414487)

Utilizator matei_cChristescu Matei matei_c Data 2 aprilie 2015 17:32:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

#define maxn 100005

int N, M, nr ;

vector<int> graf[maxn], graftr[maxn], sol[maxn] ;

int lista[maxn] ;

bool sel[maxn] ;

void dfs(int nod)
{
    sel[nod] = true ;

    for(size_t i = 0; i < graf[nod].size(); ++i)
    {
        int vecin = graf[nod][i] ;

        if( sel[vecin] == false )
            dfs(vecin) ;
    }

    lista[ ++lista[0] ] = nod ;
}

void dfstr(int nod)
{
    sel[nod] = true ;
    sol[nr].push_back(nod) ;

    for(size_t i = 0; i < graftr[nod].size(); ++i)
    {
        int vecin = graftr[nod][i] ;

        if( sel[vecin] == false )
            dfstr(vecin) ;
    }
}

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

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

    for(int i = 1; i <= M; ++i)
    {
        int x, y ;
        scanf("%d%d", &x, &y);

        graf[x].push_back(y) ;
        graftr[y].push_back(x) ;
    }

    for(int i = 1; i <= N; ++i)
        if( sel[i] == false )
            dfs(i) ;

    memset( sel, 0, sizeof(sel) ) ;

    for(int i = N; i > 0; --i)
    {
        if( sel[ lista[i] ] == false )
        {
            ++nr ;
            dfstr( lista[i] ) ;
        }
    }

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

    for(int i = 1; i <= nr; ++i)
    {
        for(size_t j = 0; j < sol[i].size(); ++j)
            printf("%d ", sol[i][j]);

        printf("\n");
    }

	return 0 ;
}