Pagini recente » Cod sursa (job #1144412) | Cod sursa (job #1211612) | Cod sursa (job #700849) | Cod sursa (job #2667123) | Cod sursa (job #3227114)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconexe.in");
ofstream cout("biconexe.out");
const int NMAX = 1e5;
int n, m, curent_time, ind;
vector<int> G[NMAX + 1];
int DFS_time[NMAX + 1];
int low[NMAX + 1];
stack<int> st;
vector<int> BCC[NMAX + 1];
void GetBCC(int node, int next_node)
{
ind++;
while(st.top() != next_node)
{
BCC[ind].push_back(st.top());
st.pop();
}
BCC[ind].push_back(st.top());
st.pop();
BCC[ind].push_back(node);
}
void DFS(int node, int dad)
{
DFS_time[node] = low[node] = ++curent_time;
st.push(node);
for(int next_node : G[node])
if(!DFS_time[next_node])
{
DFS(next_node, node);
low[node] = min(low[node], low[next_node]);
if(low[next_node] >= DFS_time[node])
GetBCC(node, next_node);
}
else if(next_node != dad)
low[node] = min(low[node], DFS_time[next_node]);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i++)
if(!DFS_time[i])
DFS(i, 0);
cout << ind << '\n';
for(int i = 1; i <= ind; i++, cout << '\n')
for(int x : BCC[i])
cout << x << ' ';
return 0;
}