Cod sursa(job #2333911)

Utilizator aditzu7Adrian Capraru aditzu7 Data 2 februarie 2019 09:34:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod{
int inf;
nod *urm;



}*l[100005],*l2[100005],*sol[100005];
int nrctc,viz2[100005],i,x,y,k,viz[100005],n,m,v[100005];
void adaug(nod *&v,int x){
nod *p;
p=new nod;
p->inf=x;
p->urm=v;
v=p;


}
void df(int i){
nod *p;
viz[i]=1;
for(p=l[i];p;p=p->urm){
    if(!viz[p->inf]){
    df(p->inf);

    }

}
 v[++k]=i;

}

void df2(int i){
nod *p;
viz2[i]=1;
 adaug(sol[nrctc],i);
for(p=l2[i];p;p=p->urm){
    if(!viz2[p->inf]){

    df2(p->inf);

    }

}


}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++){
    f>>x>>y;
adaug(l[x],y);
adaug(l2[y],x);
}
for(i=1;i<=n;i++){
    if(!viz[i]){

       df(i);
    }
}
for(i=n;i>=1;i--){
    if(!viz2[v[i]]){
nrctc++;
       df2(v[i]);
    }
}
g<<nrctc<<'\n';

for(i=1;i<=nrctc;i++){
    for(nod *j=sol[i];j;j=j->urm) g<<j->inf<<" ";
    g<<'\n';


}

    return 0;
}