Cod sursa(job #1646340)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 10 martie 2016 15:50:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#define w 100001
using namespace std;
int ll[w];
int st[w];
bool onst[w];
int idx[w];
int p,index=1,nr;
vector <int> a[w];
vector <int> rez[w];
void tarjan(int x)
{
    idx[x]=index;
    ll[x]=index;
    index++;
    st[++p]=x;
    onst[x]=1;
    int i,y;
    for (i=0;i<a[x].size();i++)
    {
        y=a[x][i];
        if (!idx[y])
        {
            tarjan(y);
            ll[x]=min(ll[x],ll[y]);
        }
        else
        {
           if (onst[y]) ll[x]=min(ll[x],idx[y]);
        }
    }
    if (ll[x]==idx[x])
    {
        nr++;
        while (st[p]!=x)
        {
            rez[nr].push_back(st[p]);
            onst[st[p]]=0;
            p--;
        }
        rez[nr].push_back(st[p]),onst[st[p]]=0,p--;
    }
}
int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    int n,m,i,j,x,y;
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
    }
    for (i=1;i<=n;i++)
        if (!idx[i]) tarjan(i);
    g<<nr<<'\n';
    for (i=nr;i>=1;i--)
    {
        for (j=rez[i].size()-1;j>=0;j--)
            g<<rez[i][j]<<' ';
        g<<"\n";
    }
    f.close();
    g.close();
    return 0;
}