Pagini recente » Cod sursa (job #2932491) | Cod sursa (job #3225133) | Cod sursa (job #2878229) | Cod sursa (job #1164721) | Cod sursa (job #2670770)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5;
int N, M;
vector <int> g[NMAX + 5];
stack <int> st;
vector < vector <int> > bix;
int tmp, discovery[NMAX + 5], low[NMAX + 5];
void dfs(int node, int parent)
{
discovery[node] = low[node] = ++tmp;
st.push(node);
for(auto it : g[node])
if(it != parent)
{
if(discovery[it] != 0)
{
low[node] = min(low[node], discovery[it]);
continue;
}
dfs(it, node);
low[node] = min(low[node], low[it]);
if(discovery[node] <= low[it])
{
vector <int> comp;
int k;
do
{
k = st.top();
st.pop();
comp.push_back(k);
}
while(k != it);
comp.push_back(node);
bix.push_back(comp);
}
}
}
int main()
{
cin >> N >> M;
for(int i = 1; i <= M; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1; i <= N; i++)
if(discovery[i] == 0)
dfs(i, -1);
cout << (int)bix.size() << '\n';
for(auto comp : bix)
{
for(auto it : comp)
cout << it << ' ';
cout << '\n';
}
return 0;
}