Cod sursa(job #332276)

Utilizator freak93Adrian Budau freak93 Data 17 iulie 2009 12:01:55
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<vector>
#include<cstring>
#include<stack>

using namespace std;

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

const int maxn=100010;

vector<int>a[maxn],answer[maxn];

int n,m,i,j,x,y,ind[maxn],lowlink[maxn],been[maxn],k;

int inde;

stack<int>S;

void tarjan(int x)
{
    ind[x]=lowlink[x]=inde;
    ++inde;
    S.push(x);
    been[x]=1;
    for(vector<int>::iterator it=a[x].begin();it!=a[x].end();++it)
        if(ind[*it]==-1)
            tarjan(*it),
            lowlink[x]=min(lowlink[x],lowlink[*it]);
        else
            if(been[*it]==1)
                lowlink[x]=min(lowlink[x],lowlink[*it]);

    if(ind[x]==lowlink[x])
    {
        ++k;
        int nod;
        do
        {
            nod=S.top();
            answer[k].push_back(nod);
            S.pop();
            been[nod]=0;
        }while(nod!=x);
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        a[x].push_back(y);
    }

    memset(ind,-1,sizeof(ind));
    for(i=1;i<=n;++i)
        if(ind[i]==-1)
            tarjan(i);

    g<<k<<"\n";

    for(i=1;i<=k;++i)
    {
        for(vector<int>::iterator it=answer[i].begin();it!=answer[i].end();++it)
            g<<*it<<" ";
        g<<"\n";
    }

    f.close();
    g.close();

    return 0;
}