Pagini recente » Cod sursa (job #1567670) | Cod sursa (job #1259910) | Cod sursa (job #1188837) | Cod sursa (job #1268921) | Cod sursa (job #3042303)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
string file = "biconex";
ifstream cin (file + ".in");
ofstream cout (file + ".out");
const int N = 1e5;
vector <int> a[N+1];
int t_in[N+1],t_min[N+1],timp;
bitset<N+1>articulatie,viz,viz2;
vector <vector<int>> comp;
void dfs (int x, int t = 0)
{
t_min[x] = t_in[x] = ++timp;
int nr_fii(0);
for (auto y : a[x])
{
if (t!=y)
{
if (t_in[y] == 0) // y este fiu al lui x in arborele DFS
{
dfs(y,x);
t_min[x] = min(t_min[x],t_min[y]);
nr_fii++;
}
else // y este ascendent (indirect) al lui x in arborele DFS
{ // => aceasta muchie este muchie de intoarcere
t_min[x] = min(t_min[x],t_in[y]);
}
}
}
if (t_min[x] == t_in[x] || (t == 0 && nr_fii > 1))
{
articulatie[x] = 1;
}
}
void dfs2(int x, int val, vector <int> &v)
{
v.push_back(x);
viz[x] = 1;
for (auto y : a[x])
{
if (t_min[y] == val && !viz[y])
{
dfs2(y,val,v);
}
}
}
int main()
{
int n,m;
cin >> n >> m;
for (int i=0; i<m; i++)
{
int x,y;
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for (int i=1; i<=n; i++)
{
if (t_in[i] == 0)
{
dfs(i,0);
}
}
for (int i=1; i<=n; i++)
{
if (!viz[i])
{
vector <int> v;
dfs2(i,t_min[i],v);
if (v.size() > 1)
comp.push_back(v);
}
viz2[i] = 1;
for (auto y : a[i])
{
if (!viz2[y] && t_min[i] != t_min[y])
{
comp.push_back({i,y});
}
}
}
cout << comp.size() << '\n';
for (auto v : comp)
{
for (auto nod : v)
cout << nod << ' ';
cout << '\n';
}
}