Pagini recente » Cod sursa (job #54315) | Cod sursa (job #3129247) | Cod sursa (job #232153) | Cod sursa (job #1729665) | Cod sursa (job #2982816)
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
string file = "biconex";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
const int N = 100001;
vector <int> L[N];
vector < vector<int> > comp;
bitset <N> viz;
int tin[N], tmin[N], t;
void dfs(int x, int anterior = 0)
{
tmin[x] = tin[x] = ++t;
for (int y : L[x])
{
if (y != anterior)
{
if (tmin[y] == 0)
dfs(y,x);
if (tmin[x] > tmin[y])
{
tmin[x] = tmin[y];
}
}
}
}
void dfs_t(int x, vector <int> &c)
{
c.push_back(x);
viz[x] = 1;
for (int y : L[x])
{
if (!viz[y])
{
if (tmin[x] != tmin[y])
{
vector <int> v = { x,y };
comp.push_back(v);
vector <int> s;
dfs_t(y, s);
if (s.size() > 1)
{
comp.push_back(s);
}
}
else
{
dfs_t(y, c);
}
}
}
}
int main()
{
int n, m, x, y, c(0);
cin >> n >> m;
while (m--)
{
cin >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
for (int i = 1; i <= n; i++)
{
if (tmin[i] == 0)
{
t = 0;
dfs(i);
}
}
for (int i = 1; i <= n; i++)
{
if (!viz[i])
{
vector <int>v;
dfs_t(i,v);
comp.push_back(v);
}
}
cout << comp.size();
for (vector <int> v : comp)
{
cout << '\n';
for (int nod : v)
cout << nod << ' ';
}
}