Cod sursa(job #627169)

Utilizator andrei.finaruFinaru Andrei Emanuel andrei.finaru Data 29 octombrie 2011 10:55:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>

using namespace std;

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

struct node
{
    int nr;
    node *next;
} *v[100005],*p,*comp[100005];

int n,m,a,b,st[100005],index[100005],lowlink[100005],k,lvl,c;
char prez[100005];

//inline int MINIM(int a, int b) {return (a<b)?a:b;}

void ctc(int i)
{
    node *q;
    index[i]=++k;
    lowlink[i]=k;
    st[++lvl]=i;
    prez[i]='1';
    q=v[i];
    while(q)
        {
            if(!index[q->nr])
            {
                ctc(q->nr);
                if(lowlink[q->nr]<lowlink[i]) lowlink[i]=lowlink[q->nr];
                //if(lowlink[i]=MINIM(lowlink[i],lowlink[q->nr]);
            }
            else if(prez[q->nr] && index[q->nr]<lowlink[i]) lowlink[i]=index[q->nr];
              //lowlink[i]=MINIM(lowlink[i],index[q->nr]);
            q=q->next;
        }
  /*  g<<i<<" * ";
    for(int q=1;q<=lvl;++q)
    {
        g<<st[q]<<' ';

    }
    g<<'\n';*/
    if(lowlink[i]==index[i])
    {
        ++c;
        while(st[lvl]!=i)
        {
            p=new node;
            p->nr=st[lvl];
            p->next=comp[c];
            comp[c]=p;
            prez[st[lvl]]='\0';
            --lvl;
        }
        p=new node;
        p->nr=i;
        p->next=comp[c];
        comp[c]=p;
        prez[i]='\0';
        --lvl;
    }
}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>a>>b;
        p=new node;
        p->nr=b;
        p->next=v[a];
        v[a]=p;
    }
    for(i=1;i<=n;++i)
        if(!index[i]) ctc(i);
    g<<c<<'\n';
    for(i=1;i<=c;++i)
    {
        p=comp[i];
        while(p) g<<p->nr<<' ', p=p->next;
        g<<'\n';
    }
    f.close(); g.close();
    return 0;
}