Cod sursa(job #1890321)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 23 februarie 2017 10:57:27
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

#define f first
#define s second

int n, m, x, y, i, j, a, b, nrComp;
int idx[100005], mini[100005];
vector<int> graph[100005];
vector<int> sol[100005];
stack<pair<int,int> > crtSol;

void DFS(int nod, int par) {
    idx[nod] = idx[par] + 1;
    mini[nod] = idx[nod];
    for(int i = 0 ; i < graph[nod].size() ; i++) {
        if(graph[nod][i] != par) {
            if(!idx[graph[nod][i]]) {
                crtSol.push(make_pair(nod, graph[nod][i]));
                DFS(graph[nod][i], nod);

                if(mini[graph[nod][i]] >= idx[nod]) {
                    a = 0;
                    b = 0;
                    nrComp++;
                    do {
                        a = crtSol.top().f;
                        b = crtSol.top().s;
                        sol[nrComp].push_back(b);
                        crtSol.pop();
                    } while (a != nod && b != graph[nod][i]);
                    sol[nrComp].push_back(a);
                }
            }

            mini[nod] = min(mini[nod], mini[graph[nod][i]]);
        }
    }
}

int main()
{
    fin>>n>>m;
    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    DFS(1, 0);

    fout<<nrComp<<'\n';
    for(i = 1 ; i <= nrComp ; i++) {
        for (j = 0 ; j < sol[i].size() ; j++)
            fout<<sol[i][j]<<' ';
        fout<<'\n';
    }

    return 0;
}