Pagini recente » Cod sursa (job #383371) | Cod sursa (job #2642883) | Cod sursa (job #2299441) | Cod sursa (job #3344863) | Cod sursa (job #3349203)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 1e5 + 1;
struct node
{
int tin, low;
} nd[NMAX];
int n, m;
struct connected_components
{
set<int> C;
} v[NMAX];
vector<int> G[NMAX];
int p[NMAX];
struct muchie
{
int x, y;
} st[NMAX];
int vf;
int cmp;
void pop_bcc(int x, int y)
{
cmp++;
while (st[vf].x != x && st[vf].y != y)
{
v[cmp].C.insert(st[vf].x);
v[cmp].C.insert(st[vf].y);
vf--;
}
v[cmp].C.insert(st[vf].x);
v[cmp].C.insert(st[vf].y);
vf--;
}
void dfs(int node, int parent)
{
static int timp = 0;
nd[node].tin = nd[node].low = ++timp;
for (int to : G[node])
{
if (!nd[to].tin) /// e nevizitat
{
st[++vf] = {node, to};
dfs(to, node);
nd[node].low = min(nd[node].low, nd[to].low);
if (nd[node].tin <= nd[to].low)
pop_bcc(node, to);
}
else if (to != parent)
{
if (nd[to].tin < nd[node].tin) /// muchie inapoi
{
st[++vf] = {node, to};
nd[node].low = min(nd[node].low, nd[to].tin);
}
}
}
}
void read()
{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
f >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
}
void afis()
{
g << cmp << '\n';
for (int i = 1; i <= cmp; i++)
{
for (auto it = v[i].C.begin(); it != v[i].C.end(); it++)
g << (*it) << ' ';
g << '\n';
}
}
int main()
{
read();
dfs(1, 0);
afis();
return 0;
}