Cod sursa(job #1647498)

Utilizator GeraltMirea Radu Geralt Data 10 martie 2016 20:52:41
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

vector <int> v[10001],vt[10001],con[10001];
int viz[10001],n,m,sign[2][1000],vizf[10001],bs;


ifstream f("ctc.in");
ofstream g("ctc.out");

void clearv(){
    int i;
for(i=1;i<=n;i++)
    viz[i]=0;
}

void clears(){
    int i,j;
for(i=0;i<=1;i++)
for(j=1;j<=n;j++)
sign[i][j]=0;

}

void DF(int i, vector <int>* a,int si){
int j;

sign[si][i]=1;

for(j=0;j<a[i].size();j++){
    if(viz[a[i][j]]==0){
            viz[a[i][j]]=1;
        DF(a[i][j],a,si);

    }
}

}


int main()
{ int x,y,i,j;

    f>>n>>m;

    for(i=1;i<=m;i++)
    f>>x>>y, v[x].push_back(y),vt[y].push_back(x);

for(i=1;i<=n;i++)
if(vizf[i]==0){
        viz[i]=1,vizf[i]=1;
DF(i,v,0);
clearv();
DF(i,vt,1);

for(j=1;j<=n;j++)
if(sign[0][j]==sign[1][j]==1){
    con[i].push_back(j);
vizf[j]=1;
}
clears();
clearv();


}
for(i=1;i<=n;i++)
    if(con[i].size())bs++;

g<<bs<<'\n';

for(i=1;i<=n;i++){
    if(con[i].size()){
    for(j=0;j<con[i].size();j++)
    g<<con[i][j]<<" ";
    g<<endl;
    }

}

    return 0;
}