Pagini recente » Cod sursa (job #809087) | Cod sursa (job #2876885) | Cod sursa (job #759301) | Cod sursa (job #2682727) | Cod sursa (job #1908207)
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100001
using namespace std;
vector <int> G[NMAX];
vector <int> BC[NMAX];
stack <pair<int,int> > st;
enum colors {white, grey, black};
int prev[NMAX], colors[NMAX];
int d[NMAX], low[NMAX];
int n, nr_c = -1;
void read_graph() {
int x, y, m;
ifstream in("biconex.in");
in >> n >> m;
for (int i = 1; i <= m; i++)
{
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
in.close();
}
void add_biconex (pair <int, int> pr)
{
nr_c++;
int ok = 1;
while (!st.empty() && st.top() != pr)
{
if (ok)
BC[nr_c].push_back(st.top().second), ok = 0;
BC[nr_c].push_back(st.top().first);
st.pop();
}
if (!st.empty())
{
if (ok)
BC[nr_c].push_back(st.top().second), ok = 0;
BC[nr_c].push_back(st.top().first);
st.pop();
}
}
void dfs(int node) {
static int time = 0;
/** **/
colors[node] = grey;
d[node] = ++time;
low[node] = d[node];
/** **/
for (unsigned int i = 0; i < G[node].size(); i++)
{
if (colors[G[node][i]] == white) {
prev[G[node][i]] = node;
st.push(make_pair(node, G[node][i]));
dfs(G[node][i]);
low[node] = min(low[node], low[G[node][i]]);
if (low[G[node][i]] >= d[node]) {
add_biconex(make_pair(node, G[node][i]));
}
} else if (prev[node] != G[node][i] && colors[G[node][i]] == grey) {
low[node] = min(low[node], d[G[node][i]]);
}
}
colors[node] = black;
}
void print_biconex() {
/** print **/
ofstream out("biconex.out");
out << nr_c + 1 << "\n";
for (int i = 0; i <= nr_c; i++)
{
for (unsigned int j = 0; j < BC[i].size(); j++)
out << BC[i][j] << " ";
out << "\n";
}
out.close();
}
int main() {
read_graph();
for (int i = 1; i <= n; i++)
if (colors[i] != black) {
dfs(i);
if (!st.empty())
add_biconex(make_pair(0, 0));
}
print_biconex();
return 0;
}