Pagini recente » Cod sursa (job #2820482) | Cod sursa (job #2460936) | Cod sursa (job #2446375) | Cod sursa (job #3162640) | Cod sursa (job #2402553)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMax = 100005;
int N, M, anc[NMax], lvl[NMax], minlvl[NMax], nc;
bool vis[NMax];
vector <int> L[NMax], Comp[NMax];
stack < int > st;
inline bool comp(const vector <int> &, const vector <int> &);
void DFS_Tree(const int &node)
{
vis[node] = 1;
minlvl[node] = lvl[node];
st.push(node);
for(int i = 0; i < L[node].size(); ++i)
{
int next = L[node][i];
if(vis[next] == 0)
{
lvl[next] = lvl[node] + 1;
anc[next] = node;
DFS_Tree(next);
minlvl[node] = min(minlvl[node], minlvl[next]);
if(minlvl[next] >= lvl[node])
{
++nc;
while(!st.empty() && st.top() != next)
{
Comp[nc].push_back(st.top());
st.pop();
}
Comp[nc].push_back(node);
st.pop();
Comp[nc].push_back(next);
}
}
else
if(next != anc[node] && minlvl[node] > lvl[next])
minlvl[node] = lvl[next];
}
}
int main()
{
in>>N>>M;
for(int i = 0; i < M; ++i)
{
int x, y;
in>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if(vis[i] == 0)
{
lvl[i] = 1;
DFS_Tree(i);
}
sort(Comp + 1, Comp + nc + 1);
out<<nc<<"\n";
for(int i = 1; i <= nc; ++i)
{
sort(Comp[i].begin(), Comp[i].end());
for(int j = 0; j < Comp[i].size(); ++j)
out<<Comp[i][j]<<" ";
out<<"\n";
}
return 0;
}
inline bool comp(const vector <int> &A, const vector <int> &B)
{
return A.size() < B.size();
}