Cod sursa(job #1649727)

Utilizator doruliqueDoru MODRISAN dorulique Data 11 martie 2016 14:50:02
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>

#include <vector>
#include <stack>
#include <cstdio>
using namespace std;

int index[100010],lowlink[100010],idx=0,nctc=0;

vector<int> lv[100010];

vector<int> ctcc[100010];
stack<int> st;

void ctc(int i)
{
    vector<int>:: iterator ii;
    ++idx;
    st.push(i);
    lowlink[i]=index[i]=idx;
    for(ii=lv[i].begin();ii!=lv[i].end();++ii)//arcul este (i,*ii)
        if(!index[*ii])
        {
            ctc(*ii);
            //la intoarcere ii fac update lu' lowlinku' astuia pe care sunt
            lowlink[i]=min(lowlink[i],lowlink[*ii]);
        }
        else
            lowlink[i]=min(lowlink[*ii],lowlink[i]);
    if(lowlink[i]==index[i])
    {
        ++nctc;
        //scot de pe stiva pina dau de i shi le bag in vector
        while(st.top()!=i)
        {
            ctcc[nctc].push_back(st.top());
            st.pop();
        }
            ctcc[nctc].push_back(st.top());
            st.pop();
    }
}

int main()
{
    FILE *f=fopen("ctc.in","r");
    int n,m,i,j,x,y;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(!index[i])
                ctc(i);
    fclose(f);
    f=fopen("ctc.out","w");
    fprintf(f,"%d\n",nctc);
    vector<int>::iterator ii;
    for(i=1;i<=nctc;i++)
    {
        for(ii=ctcc[i].begin();ii!=ctcc[i].end();++ii)
            fprintf(f,"%d ",*ii);
        fprintf(f,"\n");;
    }
    return 0;
}