Cod sursa(job #1649829)

Utilizator doruliqueDoru MODRISAN dorulique Data 11 martie 2016 15:18:13
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#define lmax 110
#include <iostream>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;

int index[lmax],lowlink[lmax],idx=0,nctc=0,epestiva[lmax];

vector<int> lv[lmax];

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

void ctc(int i)
{
    vector<int>:: iterator ii;
    ++idx;
    st.push(i);epestiva[i]=1;
    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
            if(epestiva[*ii])
                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());
            epestiva[st.top()]=0;
            st.pop();
        }
            ctcc[nctc].push_back(st.top());
            epestiva[st.top()]=0;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;
}