Cod sursa(job #1917361)

Utilizator mateigabriel99Matei Gabriel mateigabriel99 Data 9 martie 2017 12:04:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

#define NMax 100005

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int N,M;
vector<int> Graf[NMax],sol[NMax];
int mark[NMax],low[NMax],nrSol,K,Stack[NMax];

void DFS(int nod,int tata)
{
    mark[nod]=mark[tata]+1;
    low[nod]=mark[nod];
    Stack[K++]=nod;
    for(vector<int>::iterator it=Graf[nod].begin();it!=Graf[nod].end();it++)
        if(*it!=tata)
        {
            if(mark[*it]==0)
            {
                DFS(*it,nod);
                low[nod]=min(low[nod],low[*it]);
                if(low[*it]>=mark[nod])
                {
                    while(K>0 && Stack[K-1]!=*it)
                        K--, sol[nrSol].push_back(Stack[K]);
                    K--;
                    sol[nrSol].push_back(Stack[K]);
                    sol[nrSol].push_back(nod);
                    nrSol++;
                }
            }
            else
                low[nod]=min(low[nod],mark[*it]);
        }
}

int main()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y;
        fin>>x>>y;
        Graf[x].push_back(y);
        Graf[y].push_back(x);
    }

    for(int i=1;i<=N;i++)
        if(!mark[i])
            DFS(i,0);

    fout<<nrSol<<"\n";
    for(int i=0;i<nrSol;i++)
    {
        sort(sol[i].begin(),sol[i].end());
        for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
            fout<<*it<<" ";
        fout<<"\n";
    }

    return 0;
}