Pagini recente » Cod sursa (job #1873491) | Cod sursa (job #513831) | Cod sursa (job #1593479) | Cod sursa (job #1489778) | Cod sursa (job #1731689)
#include <bits/stdc++.h>
#define Nmax 100002
#define pii pair<int, int>
#define pb(x) push_back(x)
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);
using namespace std;
int N, M, low[Nmax], disc[Nmax], Time, parent[Nmax];
vector <int> G[Nmax];
stack<pii> St;
vector <int> aux;
vector< vector< int > > sol;
void read()
{
int x, y;
scanf("%d %d", &N, &M);
while(M --)
{
scanf("%d %d", &x, &y);
G[x].pb(y);
G[y].pb(x);
}
}
int Min(int x, int y)
{
return x < y ? x : y;
}
void Form_BCC(pair <int, int> p)
{
pair <int, int> x;
do
{
x = St.top();
St.pop();
aux.pb(x.first);
aux.pb(x.second);
}
while(x != p);
sort(aux.begin(), aux.end());
aux.erase(unique(aux.begin(), aux.end()), aux.end());
sol.pb(aux);
aux.clear();
}
void BCC(int u)
{
/// // Initialize discovery time and low value
disc[u] = low[u] = ++ Time;
/// Go through all vertices adjacent to this
vector<int> :: iterator i;
for (i = G[u].begin(); i != G[u].end(); ++ i)
{
int v = *i;
/// If v is not visited the recur for it
if(!disc[v]) /// tree edge
{
St.push(make_pair(u, v));
parent[v] = u;
BCC(v);
low[u] = Min(low[u], low[v]);
///If u is an articulation point,
///pop all edges from stack till u -- v
if(low[v] >= disc[u]) /// v - articulation point
Form_BCC(make_pair(u, v));
}
else if(v != parent[u] && disc[v] < low[u]) /// back edge
{
St.push(make_pair(u, v));
low[u] = Min(low[u], disc[v]);
}
}
}
void solve()
{
for(int i = 1; i <= N; ++ i)
if(!disc[i]) BCC(i);
}
void write()
{
int sz = sol.size();
printf("%d\n", sz);
for(int i = 0; i < sz; i++)
{
int szp = sol[i].size();
for(int j = 0; j < szp; ++ j)
{
printf("%d ", sol[i][j]);
}
printf("\n");
}
}
int main()
{
read();
solve();
write();
return 0;
}