Pagini recente » Diferente pentru autumn-warmup-2007/solutii/runda-2 intre reviziile 56 si 39 | Cod sursa (job #2002805) | Cod sursa (job #3243090) | Cod sursa (job #1392414) | Cod sursa (job #3041698)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//ifstream cin("biconex.in");
//ofstream cout("biconex.out");
const int nmax = 1e5 + 5;
stack <int> st;
int parent[nmax], disc[nmax], low[nmax];
int cnt, id;
vector <int> edge[nmax];
vector <int> comp[nmax];
void dfs(int node)
{
disc[node] = low[node] = ++cnt;
st.push(node);
for(int i = 0; i < edge[node].size(); i++){
int child = edge[node][i];
if(child == parent[node])
continue;
if(disc[child]){
low[node] = min(low[node], disc[child]);
continue;
}
dfs(child);
low[node] = min(low[node], low[child]);
if(low[child] >= disc[node]){
id++;
while(st.top() != child){
comp[id].push_back(st.top());
st.pop();
}
comp[id].push_back(child);
comp[id].push_back(node);
st.pop();
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(disc[i] == 0){
cnt = 0;
dfs(1);
}
cout << id << "\n";
for(int i = 1; i <= id; i++){
for(int j = 0; j < comp[i].size(); j++)
cout << comp[i][j] << " ";
cout << "\n";
}
return 0;
}