Pagini recente » Istoria paginii runda/simulare_fmi_nostress_3 | Cod sursa (job #1539607) | Monitorul de evaluare | Cod sursa (job #996445) | Cod sursa (job #2476302)
#include <bits/stdc++.h>
#define endl "\n"
#define MaxN 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define cin fin
#define cout fout
int n, m, x, y;
vector <int> adj[MaxN];
vector<int > dfn, low;
vector< vector <int> > C;
stack <pair <int, int> > stk;
void read()
{
cin >> n >> m;
for(int i=1; i<=m; i++)
{
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void scoateStiva(int x, int y)
{
vector <int> con;
int tx;
int ty;
do
{
tx = stk.top().first;
ty = stk.top().second;
stk.pop();
con.push_back(tx);
con.push_back(ty);
} while(tx != x || ty != y);
C.push_back(con);
}
void DFS(int n, int fn, int number)
{
dfn[n] = low[n] = number;
for(const auto& i: adj[n])
{
if(i == fn)
{
continue;
}
if(dfn[i] == -1)
{
stk.push( make_pair(n, i));
DFS(i, n, number+1);
low[n] = min(low[n], low[i]);
if(low[i] >= dfn[n])
{
scoateStiva(n, i);
}
}
else
{
low[n] = min(low[n], dfn[i]);
}
}
}
void solve()
{
dfn.resize(n+1);
dfn.assign(n+1, -1);
low.resize(n+1);
DFS(1, 0, 0);
cout << C.size() << endl;
for(int i=0; i < C.size(); i++)
{
sort(C[i].begin(), C[i].end());
C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
for(int j=0; j < C[i].size(); j++)
{
cout << C[i][j] << " ";
}
cout << endl;
}
}
int main()
{
read();
solve();
}