Cod sursa(job #1848663)

Utilizator DavidDragulinDragulin David DavidDragulin Data 16 ianuarie 2017 13:43:19
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g ("ctc.out");
short a[10001][10001],ll;
struct nod
{
    int inf;
    nod *urm;
} *l[101], *lt[101];

int n, viz[101], st[101], k;

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

}

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


void DF2(int i)
{
    nod *c;
    viz[i]=1;
    a[ll][a[ll][0]+1]=i;
    a[ll][0]++;
    for(c=lt[i]; c!=NULL; c=c->urm)
        if (!viz[c->inf]) DF2(c->inf);
}

int main()
{
    int i, x, y,m,j=0;
    f>>n>>m;
    while (f>>x>>y)
    {
        adaug(l[x],y); // liste de adiacenta graful initial
        adaug(lt[y],x); // liste de adiacenta graful transpus
        //(obtinut prin inversarea sensurilor arcelor)
    }


    for (i=1; i<=n; i++)
        if (!viz[i]) DF1(i);

    memset (viz,0, sizeof(viz));

    for (i=n; i>=1; i--)
        if (!viz[st[i]])
        {
            ll++,DF2(st[i]);
        }
    g<<ll<<'\n';
    for(i=1;i<=ll;i++)
    {
        for(j=1;j<=a[i][0];j++)
            g<<a[i][j]<<" ";
        g<<'\n';
    }
    g.close();
    return 0;
}