Cod sursa(job #681735)

Utilizator adrian401NAN NAN adrian401 Data 17 februarie 2012 18:12:04
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
//
//  main.cpp
//  ctc2
//
//  Created by Nenu Adrian on 2/17/12.
//  Copyright 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <vector>
#include<algorithm>

using namespace std;

vector <int> G[100100], GT[100100], S[100100], A;
int n,m,x,y,i,viz[100100],T[100100],sol,nr,j;
void df(int nod){
    viz[nod]=1;
    for (int i = 0; i < (int) G[nod].size(); ++ i){
        if(!viz[G[nod][i]])
            df(G[nod][i]);
    }
    T[nod] = ++ nr; 
}

void dff(int nod){
    viz[nod]=1;
    S[sol].push_back(nod);
    for (int i = 0; i < (int) GT[nod].size(); ++ i){
        if(!viz[GT[nod][i]])
            dff(GT[nod][i]);
    }
    
}
inline bool  cmp(int a, int b){
    return (T[a]>T[b]);
}
int main (int argc, const char * argv[])
{

    ifstream f("ctc.in");
	ofstream g("ctc.out");
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        if(!viz[i])
            df(i);
    }
     for(i=1;i<=n;++i){
         A.push_back(i);
         viz[i]=0;
    }
    
    sort(A.begin(),A.end(),cmp);
    
    for(i=0;i<n;i++)
        if(!viz[A[i]]){
            sol++;
            dff(A[i]);
        }
    
    g<<sol<<endl;
    for(i=1; i<=sol; i++){
       	for (j = 0; j < (int) S[i].size(); ++ j)
            g<<S[i][j]<<" ";
        g<<endl;
        
    }
        
    return 0;
}