Cod sursa(job #2170067)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 14 martie 2018 22:15:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include<stdio.h>
#include<algorithm>
#define MAXV 100000
#define MAXE 200000
void dfs(int nod);
void dfstati(int nod);
int lista[MAXV+1],next[MAXE+1],val[MAXE+1],k=0;
int level[MAXV+1];
int ind[MAXV+1];
bool viz[MAXV+1];
std::vector<std::vector<int>> sol;
std::vector<int> partial_sol;
int st[MAXV+1],ult=-1;
int on_stack[MAXV+1];
int index=0;
FILE*fin,*fout;
int main()
{
    fin=fopen("ctc.in","r");
    fout=fopen("ctc.out","w");
    int V,E;
    fscanf(fin,"%d %d",&V,&E);
    for(int i=1; i<=E; i++)
    {
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        next[++k]=lista[x];
        val[k]=y;
        lista[x]=k;
    }
    for(int i=1;i<=V;i++)
    {
        if(!viz[i])
        {
            viz[i]=1;
            dfs(i);
        }
    }
    fprintf(fout,"%d\n",sol.size());
    for(int i=0;i<sol.size();i++)
    {
        for(int j=0;j<sol[i].size();j++)
        {
            fprintf(fout,"%d ",sol[i][j]);
        }
        fprintf(fout,"\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
void dfs(int nod)
{
    index++;
    level[nod]=index;
    ind[nod]=index;
    st[++ult]=nod;
    on_stack[nod]=1;
    int p=lista[nod];
    while(p!=0)
    {
        int vec=val[p];
        if(!viz[vec])
        {
            viz[vec]=1;
            dfs(vec);
            level[nod]=std::min(level[nod],level[vec]);
        }
        else if(on_stack[vec])
        {
            level[nod]=std::min(level[nod],ind[vec]);
        }
        p=next[p];
    }
    if(ind[nod]==level[nod])
    {
        partial_sol.clear();
        while(st[ult]!=nod && ult>=0)
        {
            partial_sol.push_back(st[ult]);
            on_stack[st[ult]]=0;
            ult--;
        }
        partial_sol.push_back(nod);
        ult--;
        on_stack[nod]=0;
        sol.push_back(partial_sol);
    }
}