Cod sursa(job #976121)

Utilizator andrettiAndretti Naiden andretti Data 22 iulie 2013 16:33:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<stack>
#include<vector>
#define pb push_back
#define maxn 100005
using namespace std;

int n,m,nr,pas;
int low[maxn],ind[maxn],v[maxn];
vector <int> l[maxn],sol[maxn];
stack <int> s;

void cit()
{
    int i;
    int x,y;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        l[x].pb(y);
    }
}

void add(int k)
{
    int i;

    nr++;
    while(s.top()!=k)
    {
        sol[nr].pb(s.top());
        v[s.top()]=0;
        s.pop();
    }

    sol[nr].pb(k);
    v[s.top()]=0;
    s.pop();
}

void df(int k)
{

    pas++;
    s.push(k); v[k]=1;
    low[k]=ind[k]=pas;
    for(unsigned int i=0;i<l[k].size();i++)
        if(ind[l[k][i]]==0)
        {
            df(l[k][i]);
            low[k]=min(low[k],low[l[k][i]]);
        }
        else
         if(v[l[k][i]])
          low[k]=min(low[k],ind[l[k][i]]);


    if(low[k]==ind[k])
       add(k);
}

void afis()
{
    int k,i;

    printf("%d\n",nr);
    for(k=1;k<=nr;k++)
    {
        for(unsigned int i=0;i<sol[k].size();i++)
          printf("%d ",sol[k][i]);
        printf("\n");
    }
}

int main()
{
    int aux;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    cit();
    for(int i=1;i<=n;i++)
        if(ind[i]==0)
            df(i);


   afis();

    fclose(stdin);
    fclose(stdout);
    return 0;
}