Cod sursa(job #977689)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 26 iulie 2013 13:48:45
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
using namespace std;
ofstream g("ctc.out");
int v[100001],vr[200001],kr,nr;
struct la
{
    la *urm;
    int ind;
} *p1,*q;
struct nod
{
    la *urm;
    int b;
    int index,mn;
} vnod[100001];
int index1,nv,n,m,i,x,y;
void analyze(int pos)
{
    vnod[pos].b=1;
    index1++;
    nv++;
    v[nv]=pos;
    la *p;
    p=vnod[pos].urm;
    vnod[pos].index=index1;
    vnod[pos].mn=index1;
    while (p!=NULL)
    {
        if (vnod[p->ind].b==0)
            analyze(p->ind);
        vnod[pos].mn=min(vnod[pos].mn,vnod[p->ind].mn);
        p=p->urm;
    }
    if (vnod[pos].index==vnod[pos].mn)
    {
        kr++;
        while (v[nv]!=pos)
        {
            nr++;
            vr[nr]=v[nv];
            vnod[v[nv]].mn=999999999;
            v[nv]=0;
            nv--;
        }
        nr++;
        vr[nr]=v[nv];
        v[nv]=0;
        nv--;
        nr++;
        vr[nr]=-1;
    }
}
int main(void)
{
    FILE * f;
    f=fopen("ctc.in","r");
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        if (vnod[x].urm==NULL)
        {
            p1=new(la);
            p1->ind=y;
            vnod[x].urm=p1;
            p1->urm=NULL;
        }
        else
        {
            q=vnod[x].urm;
            while (q->urm!=NULL)
                q=q->urm;
            p1=new(la);
            p1->ind=y;
            p1->urm=NULL;
            q->urm=p1;
        }
    }
    for (i=1;i<=n;i++)
        if (vnod[i].b==0)
            analyze(i);
    g<<kr<<'\n';
    for (i=1;i<=nr;i++)
        if (vr[i]==-1)
            g<<'\n';
        else
            g<<vr[i]<<' ';
    g.close();
    return 0;
}