Cod sursa(job #2333920)

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

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



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


}
void tarjan(int x){
st[++k]=x;viz[x]=1;
idx[x]=lowlink[x]=++index;
for(nod *p=l[x];p;p=p->urm){
    int y=p->inf;
    if(!idx[y]){
        tarjan(y);
        lowlink[x]=min(lowlink[x],lowlink[y]);



    }
    else if(viz[y])    { lowlink[x]=min(lowlink[x],lowlink[y]);
    }
}
if(idx[x]==lowlink[x]){nrctc++;
int ww;
do { ww=st[k];
k--;
viz[ww]=0;
 adaug(sol[nrctc],ww);
}while(ww!=x);
}
}

int main()
{
f>>n>>m;
for(i=1;i<=m;i++){
    f>>x>>y;
adaug(l[x],y);
}
for(i=1;i<=n;i++)
    if(!idx[i])tarjan(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;
}