Cod sursa(job #627157)

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

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];
vector <int> aux;
vector <int> :: iterator it, o;
vector < vector<int> > comp;

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);
                lowlink[i]=MINIM(lowlink[i],lowlink[q->nr]);
            }
            else if(prez[q->nr]) lowlink[i]=MINIM(lowlink[i],index[q->nr]);
            q=q->next;
        }
    if(lowlink[i]==index[i])
    {
        ++c;
        aux.clear();
        while(st[lvl]!=i)
        {
            /*p=new node;
            p->nr=st[lvl];
            p->next=comp[c];
            comp[c].nr=st[lvl];*/
            aux.push_back (st[lvl]);
            prez[st[lvl]]='\0';
            --lvl;
        }
        /*p=new node;
        p->nr=i;
        p->next=comp[c];
        comp[c]=p;*/
        aux.push_back (i);
        comp.push_back (aux);
        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';
    }*/
    for(i=0;i<c;++i)
    {
        o=comp[i].end();
        for(it=comp[i].begin(); it!=o; ++it) g<<*it<<' ';
        g<<'\n';
    }
    f.close(); g.close();
    return 0;
}