Cod sursa(job #1552825)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 decembrie 2015 19:00:59
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
 
#define NMax 100010
 
using namespace std;
 
ifstream f("biconex.in");
ofstream g("biconex.out");
 
int nodes, edges, prenum[NMax], low[NMax], pren, father[NMax], numComp;
bool mark[NMax], alreadyDisp[NMax];
vector<int> G[NMax], biComp[NMax];
 
struct edge {
    int n1;
    int n2;
};
stack<edge> mStack;
 
int getMin(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
 
void DFS(int node)
{
    mark[node] = true;
 
    prenum[node] = ++pren;
    low[node] = pren;
 
    for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
        edge edg;
        edg.n1 = node;
        edg.n2 = *it;
        if (!mark[*it]) {
            mStack.push(edg);
 
            father[*it] = node;
 
            DFS(*it);
 
            low[node] = getMin(low[node], low[*it]);
 
            if (low[*it] >= prenum[node]) {
                ++numComp;
 
                while (mStack.top().n1 != node && mStack.top().n2 != *it) {
                    biComp[numComp].push_back(mStack.top().n1);
                    biComp[numComp].push_back(mStack.top().n2);
                    mStack.pop();
                }
                biComp[numComp].push_back(node);
                biComp[numComp].push_back(*it);
            }
        }
        else if ((father[node] != *it) && (prenum[*it] < prenum[node])) {
            mStack.push(edg);
            low[node] = getMin(low[node], low[*it]);
        }
    }
 
     
}
 
int main()
{
    f >> nodes >> edges;
 
    int n1, n2;
 
    for (int i = 1; i <= edges; i++) {
        f >> n1 >> n2;
 
        G[n1].push_back(n2);
        G[n2].push_back(n1);
    }
 
    for (int i = 1; i <= nodes; i++) {
        if (!mark[i])
            DFS(i);
 
        g << numComp << "\n";
 
        for (int i = 1; i <= numComp; i++) {
            memset(alreadyDisp, 0, sizeof(alreadyDisp));
 
            for (vector<int>::iterator it = biComp[i].begin(); it != biComp[i].end(); it++) {
                if (!alreadyDisp[*it]) {
                    g << *it << " ";
                    alreadyDisp[*it] = true;
                }
            }
            g << "\n";
        }
 
        return 0;
    }
}