Cod sursa(job #2012378)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 18 august 2017 17:04:57
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100000 + 5;
const int MMAX = 100000 + 5;

struct Edge {
    int a, b;
    inline int other(int node) {
        return a ^ b ^ node;
    }
} edges[MMAX];

vector <int> graph[NMAX];

int h[NMAX];
int low[NMAX];
bool vis[NMAX];

stack <int> stk;

vector <vector <int> > bic;

void dfs(int node, int fatherEdge) {
    vis[node] = true;
    //bool isCritical = false;
    int sons = 0;
    for (auto it: graph[node]) {
        int son = edges[it].other(node);
        if (!vis[son]) {
            ++ sons;
            h[son] = low[son] = 1 + h[node];
            stk.push(it);
            dfs(son, it);
            low[node] = min(low[node], low[son]);
            
            //Critical edge
            //if (low[son] > h[node])
            //    cout << "Critical " << edges[it].a << ' ' << edges[it].b << endl;
            
            //Critical node
            //if (low[son] >= h[node])
            //    isCritical = true;
        
            if (low[son] >= h[node]) {
                bic.push_back(vector <int>());
                int last;
                do {
                    last = stk.top();
                    stk.pop();
                    bic.back().push_back(edges[last].a);
                    bic.back().push_back(edges[last].b);
                } while (last != it);
                vector <int> &v = bic.back();

                sort(v.begin(), v.end());
                v.resize(unique(v.begin(), v.end()) - v.begin());
            }
        }
        else if (h[son] < h[node] && it != fatherEdge) {
            low[node] = min(low[node], h[son]);
            //stk.push(it);
        }
    }

    //Critical node
    /*if (fatherEdge == 0) {
        if (sons > 1)
            cout << "Critical node " << node << endl;
    }
    else if (isCritical)
        cout << "Critical node " << node << endl;*/
}

int main() {
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");

    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= M; ++ i) {
        cin >> edges[i].a >> edges[i].b;
        if (edges[i].a != edges[i].b) {
            graph[edges[i].a].push_back(i);
            graph[edges[i].b].push_back(i);
        }
    }

    dfs(1, 0);
    
    cout << bic.size() << '\n';
    for (auto it: bic)
        for (int i = 0; i < it.size(); ++ i)
            cout << it[i] << " \n"[i + 1 == it.size()];
    return 0;
}