Cod sursa(job #2145277)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 27 februarie 2018 11:23:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

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

struct nod {
    int inf;
    nod *urm;
}*l[100005],*lt[100005];

int n,m,viz[100005],st[100005],nr,nr2,ok2;

void adaug(nod*&p,int x) {
    nod *c;
    c=new nod;
    c->urm=p;
    c->inf=x;
    p=c;
}

void df(int k) {
    nod *c;
    viz[k]=1;
    for (c=l[k];c;c=c->urm)
        if (!viz[c->inf])
            df(c->inf);
    st[++nr]=k;
}

void df2(int k) {
    nod *c;
    viz[k]=1;
    if (ok2)
        g<<k<<' ';
    for (c=lt[k];c;c=c->urm)
        if (!viz[c->inf])
            df2(c->inf);
}

int main() {
    int i,x,j,y,ok;
    nod *c;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y;
        adaug(l[x],y);
        adaug(lt[y],x);
    }
    for (i=1;i<=n;i++)
        if (!viz[i])
            df(i);
    for (i=1;i<=n;i++)
        viz[i]=0;
    for (i=n;i>=1;i--)
        if (!viz[st[i]]) {
            df2(st[i]);
            nr2++;
        }
    ok2=1;
    g<<nr2<<'\n';
    for (i=1;i<=n;i++)
        viz[i]=0;
    for (i=n;i>=1;i--)
        if (!viz[st[i]]) {
            df2(st[i]);
            g<<'\n';
        }
    return 0;
}