Pagini recente » Cod sursa (job #470354) | Cod sursa (job #2120407) | Cod sursa (job #1712873) | Cod sursa (job #2288279) | Cod sursa (job #3240447)
#include <bits/stdc++.h>
const std :: string FILENAME = "biconex";
std :: ifstream in (FILENAME + ".in");
std :: ofstream out (FILENAME + ".out");
const int NMAX = 1e5 + 5;
int n;
int m;
int x;
int y;
int cnt;
int tin[NMAX];
int low[NMAX];
std :: vector <int> v[NMAX];
std :: bitset <NMAX> visited;
std :: stack <int> s;
std :: vector <int> comp;
std :: vector <std :: vector <int>> comps;
void dfs(int nod)
{
tin[nod] = low[nod] = cnt ++;
s.push(nod);
for(int i : v[nod])
{
if(visited[i] == false)
{
visited[i] = true;
dfs(i);
low[nod] = std :: min(low[nod], low[i]);
if(low[i] >= tin[nod])
{
comp.clear();
while(s.top() != i)
{
comp.push_back(s.top());
s.pop();
}
comp.push_back(s.top());
s.pop();
comp.push_back(nod);
comps.push_back(comp);
}
}
else
{
low[nod] = std :: min(low[nod], tin[i]);
}
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i ++)
{
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);
out << comps.size() << '\n';
for(int i = 0; i < comps.size(); i ++)
{
std :: sort(comps[i].begin(), comps[i].end());
for(int j : comps[i])
{
out << j << " ";
}
out << '\n';
}
return 0;
}