Pagini recente » Cod sursa (job #1316614) | Cod sursa (job #1539646) | Cod sursa (job #1534598) | Cod sursa (job #302534) | Cod sursa (job #2025929)
#include <bits/stdc++.h>
using namespace std;
#define FILE_IO
typedef pair<int, int> pii;
int N, M;
int h[100005], grd[100005], low[100005];
vector<pii> edges;
set<int> edg[100005];
bool art[100005], done[100005];
vector<int> cmp;
vector< vector<int> > bcc;
int DFS(int nod, int fth)
{
h[nod] = h[fth] + 1;
low[nod] = h[nod];
int sons = 0;
for(auto nxt: edg[nod])
{
if(nxt == fth) continue;
if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }
DFS(nxt, nod);
if(low[nxt] >= h[nod]) art[nod] = 1;
low[nod] = min(low[nod], low[nxt]);
sons++;
}
return sons;
}
bool bridge(int x, int y)
{
if(h[x] > h[y]) swap(x, y);
if(low[y] > h[x]) return true;
return false;
}
void DFS2(int nod)
{
if(done[nod]) return;
done[nod] = 1;
cmp.push_back(nod);
for(auto nxt: edg[nod])
DFS2(nxt);
}
int main()
{
#ifdef FILE_IO
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#endif
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edg[x].insert(y);
edg[y].insert(x);
edges.push_back({x, y});
grd[x]++, grd[y]++;
}
int sns = DFS(1, 0);
if(sns > 1) art[1] = 1;
for(auto e: edges)
if( bridge(e.first, e.second) )
{
edg[e.first].erase(e.second);
edg[e.second].erase(e.first);
cmp.clear();
cmp.push_back(e.first);
cmp.push_back(e.second);
bcc.push_back(cmp);
}
for(int i = 1; i <= N; i++)
if(!done[i] && !edg[i].empty())
{
cmp.clear();
DFS2(i);
bcc.push_back(cmp);
}
printf("%d\n", bcc.size());
for(auto v: bcc)
{
sort(begin(v), end(v));
for(auto x: v) printf("%d ", x);
printf("\n");
}
return 0;
}