Pagini recente » Cod sursa (job #2568092) | Cod sursa (job #2364684) | Cod sursa (job #2620550) | Cod sursa (job #2846910) | Cod sursa (job #2126117)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
int N, M, indexGlobal = 1;
struct nod
{
int index, lowlink;
}v[NMAX];
vector <vector <int> > sol;
vector <int> G[NMAX];
stack <pair <int, int> > S;
void read()
{
scanf("%d %d", &N, &M);
for(int i=1; i<=M; ++i)
{
int a, b;
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
}
void adaugareComponenta(int node)
{
vector <int> componenta;
while(S.top().second != node)
{
componenta.push_back(S.top().second);
S.pop();
}
componenta.push_back(S.top().second);
componenta.push_back(S.top().first);
S.pop();
sol.push_back(componenta);
}
void dfs(int node, int tata)
{
v[node].index = v[node].lowlink = indexGlobal;
indexGlobal++;
vector <int>::iterator it;
for(it = G[node].begin(); it != G[node].end(); ++it)
{
if(*it == tata)
continue;
if(v[*it].index == 0)
{
S.push(make_pair(node, *it));
dfs(*it, node);
v[node].lowlink = min(v[node].lowlink, v[*it].lowlink);
if(v[*it].lowlink >= v[node].index)
adaugareComponenta(*it);
}
else
v[node].lowlink = min(v[node].lowlink, v[*it].index);
}
}
void solve()
{
for(int i=1; i<=N; ++i)
if(v[i].index == 0)
dfs(i, 0);
}
void print()
{
printf("%d\n", sol.size());
vector <vector <int> >::iterator itSol;
for(itSol = sol.begin(); itSol != sol.end(); ++itSol)
{
vector <int>::iterator it;
for(it = itSol->begin(); it != itSol->end(); ++it)
printf("%d ", *it);
printf("\n");
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
read();
solve();
print();
return 0;
}