Cod sursa(job #2106147)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 15 ianuarie 2018 09:28:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>

#define INF 2140000000
#define MOD 1000000007
#define MaxN 100005

using namespace std;

FILE *IN=fopen("biconex.in","r"),*OUT=fopen("biconex.out","w");

vector <int> Graph[MaxN],junk;

int N,M,X,Y,L[MaxN],D[MaxN];
vector<pair<int,int> >Stack;
vector<vector<int> >Comp;
void WriteComponent(int node)
{
    bool stop=0;
    Comp.push_back(junk);
    while(!stop)
    {
        if(node==Stack[Stack.size()-1].second)
            stop=1;
        Comp[Comp.size()-1].push_back(Stack[Stack.size()-1].first);
        Stack.pop_back();
    }
    Comp[Comp.size()-1].push_back(node);
}
void DFS(int node,int father)
{
    D[node]=L[node]=1+D[father];
    for(int i=0;i<Graph[node].size();i++)
    {
        if(!D[Graph[node][i]])
        {
            Stack.push_back({Graph[node][i],node});
            DFS(Graph[node][i],node);
            L[node]=min(L[node],L[Graph[node][i]]);
            if(L[Graph[node][i]]>=D[node])
                WriteComponent(node);
        }
        else L[node]=min(L[node],D[Graph[node][i]]);
    }
}

int main()
{
    fscanf(IN,"%d %d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(IN,"%d %d",&X,&Y);
        Graph[X].push_back(Y);
        Graph[Y].push_back(X);
    }
    for(int i=1;i<N;i++)
        if(!D[i])DFS(i,0);
    fprintf(OUT,"%d\n",Comp.size());
    for(int i=0;i<Comp.size();i++)
    {
        for(int j=0;j<Comp[i].size();j++)
            fprintf(OUT,"%d ",Comp[i][j]);
        fprintf(OUT,"\n");
    }
    return 0;
}