Pagini recente » Cod sursa (job #3285674) | Cod sursa (job #3262640) | Cod sursa (job #3293762) | Cod sursa (job #3293462) | Cod sursa (job #3292683)
#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 1e5+5;
int n, m, cb, fr[NMAX], ord[NMAX], low[NMAX], k, st[NMAX], top;
vector<int> adj[NMAX], comp[NMAX];
void dfs(int i, int p)
{
fr[i] = 1;
st[++top] = i;
ord[i] = low[i] = ++k;
for (int j : adj[i])
{
if (j == p)
continue;
if (fr[j])
low[i] = min(low[i], ord[j]);
else
{
dfs(j, i);
low[i] = min(low[i], low[j]);
if (low[j] >= ord[i]) /// i nod critic
{
cb++;
while (st[top] != j)
comp[cb].push_back(st[top--]);
comp[cb].push_back(j);
top--;
comp[cb].push_back(i);
}
}
}
return;
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!fr[i])
dfs(i, 0);
fout << cb << nl;
for (int i = 1; i <= cb; i++)
{
for (int j : comp[i])
fout << j << ' ';
fout << nl;
}
return 0;
}