Cod sursa(job #2199794)

Utilizator RaduVFVintila Radu-Florian RaduVF Data 29 aprilie 2018 02:22:38
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 200005
using namespace std;

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

int n, m, counter;
int visited[NMAX], stage[NMAX], lowStage[NMAX], father[NMAX];
vector <int> edges[MMAX], component[MMAX];
stack < pair <int, int> > edge;
pair <int, int> aux;

void CreateComponent(int node, int neighbor) {
    ++counter;
    do {
        aux=edge.top();
        component[counter].push_back(aux.first);
        component[counter].push_back(aux.second);
        edge.pop();
    }
    while((aux.first!=node ||
           aux.second!=neighbor) &&
          (aux.second!=node ||
           aux.first!=neighbor));
}

void DFS(int node) {
    visited[node]=1;
    lowStage[node]=stage[node];
    for(unsigned i=0; i<edges[node].size(); ++i) {
        int neighbor = edges[node][i];
        if(stage[neighbor]<stage[node] && neighbor!=father[node]) {
            edge.push(make_pair(node, neighbor));
            if(!visited[neighbor]) {
                stage[neighbor]=stage[node]+1;
                father[neighbor]=node;
                DFS(neighbor);
                if(lowStage[node]>lowStage[neighbor]) lowStage[node]=lowStage[neighbor];
                if(lowStage[neighbor]>=stage[node]) CreateComponent(node, neighbor);
            }
            else if(lowStage[node]>stage[neighbor] && neighbor!=father[node]) lowStage[node]=stage[neighbor];
        }
    }
}

int main() {
    int x,y;
    fin>>n>>m;
    for(int i=1; i<=m; ++i) {
        fin>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    visited[1]=1; stage[1]=1; DFS(1);
    fout<<counter<<endl;
    for(int i=1; i<=counter; ++i) {
        sort(component[i].begin(), component[i].end());
        fout<<component[i][0]<<' ';
        for(unsigned j=1; j<component[i].size(); ++j)
            if(component[i][j]!=component[i][j-1]) fout<<component[i][j]<<' ';
        fout<<endl;
    }
    return 0;
}