Pagini recente » Cod sursa (job #2866278) | Cod sursa (job #2365469) | Cod sursa (job #735355) | Cod sursa (job #2557576) | Cod sursa (job #2864034)
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define Nmax 300001
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
typedef vector <int> VI;
stack <int> S;
int id, n, m, x, y, h;
int Low_Link[Nmax], Id[Nmax];
VI V[Nmax], Ans[Nmax];
void Biconex(int vertex, int dad){
id++;
S.push(vertex);
Low_Link[vertex] = Id[vertex] = id;
for(int new_vertex : V[vertex]){
if(new_vertex == dad)
continue;
if(Low_Link[new_vertex] == 0){
Biconex(new_vertex, vertex);
Low_Link[vertex] = min(Low_Link[vertex], Low_Link[new_vertex]);
if(Low_Link[new_vertex] >= Id[vertex]){
Ans[++h].push_back(vertex);
int x = 0;
do{
x = S.top();
Ans[h].push_back(x);
S.pop();
}while(x != new_vertex);
}
}
else Low_Link[vertex] = min(Low_Link[vertex], Id[new_vertex]);
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; ++i){
fin >> x >> y;
V[x].push_back(y);
V[y].push_back(x);
}
Biconex(1, -1);
for(int i = 1; i <= h; ++i){
fout << Ans[i].size() << '\n';
for(int j : Ans[i])
fout << j << " ";
fout << "\n";
}
return 0;
}