Pagini recente » Cod sursa (job #3176614) | Cod sursa (job #885729) | Cod sursa (job #1789904) | Cod sursa (job #1898941) | Cod sursa (job #3041699)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int nmax = 1e5 + 5;
int parent[nmax], depth[nmax], low[nmax];
vector <int> edge[nmax];
vector <int> comp[nmax];
int id, cnt;
stack <int> st;
void dfs(int node)
{
depth[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(depth[child]){
low[node] = min(low[node], depth[child]);
continue;
}
parent[child] = node;
dfs(child);
low[node] = min(low[node], low[child]);
if(low[child] >= depth[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(depth[i] == 0){
cnt = 0;
dfs(i);
}
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;
}