Cod sursa(job #999381)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 20 septembrie 2013 01:15:09
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define forEACH(G,it) for(vector<int>::iterator it=G.begin();it!=G.end();++it)
using namespace std;
const int Nmax = 100005;

vector <int> G[ Nmax ], Gt[ Nmax ];// graf, graf transpus
vector<int> solution[ Nmax ];
stack <int> answer;
bitset< Nmax > used;
int tare[ Nmax ],N,M,nrt;

void get_graphs(){
    scanf("%d%d",&N,&M);
    int x,y;
    FOR(i,1,M){
        scanf("%d%d",&x,&y);
        G[ x ].push_back(y);
        Gt[ y ].push_back(x);
    }
}

void DFS(int nodc){
    used[ nodc ] = true;
    tare[ nodc ] = max( 1 , tare[ nodc ]);
    forEACH(G[ nodc ],it)
        if(!used[*it])
            DFS(*it);
}

void DFS_T(int nodc){
    used[ nodc ] = true;
    if(tare[ nodc ] == 1)
            answer.push(nodc),tare[nodc] = 2;
    forEACH(Gt[ nodc ],it)
        if(!used[*it])
            DFS_T(*it);
}

void baga_sol(){
    while(!answer.empty()){
        solution[nrt].push_back(answer.top());
        answer.pop();
    }
    ++nrt;
}

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

    get_graphs();

    FOR(i,1,N)
        if(tare[ i ] != 2){
            DFS(i);
            FOR(j,1,N)
                used [ j ] = false;
            DFS_T(i);
            baga_sol();
        }
    printf("%d\n",nrt);
    FOR(i,0,(nrt-1)){
        FOR(j,0,(solution[i].size()-1))
            printf("%d ",solution[i][j]);
        printf("\n");
    }
    return 0;
}