Pagini recente » Monitorul de evaluare | Cod sursa (job #3353568) | Cod sursa (job #3306252) | Cod sursa (job #2954597) | Cod sursa (job #3318951)
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100005];
int low[100005], timp[100005], ct, viz[100005];
deque <pair<int, int>> q;
vector<vector<int>> b;
void new_bix(int x, int y)
{
vector <int> p;
unordered_set<int> unic;
while(q.back().first != x && q.back().second != y)
unic.insert(q.back().first), unic.insert(q.back().second), q.pop_back();
unic.insert(q.back().first), unic.insert(q.back().second), q.pop_back();
for(unordered_set <int> :: iterator i = unic.begin(); i != unic.end(); i ++)
p.push_back(*i);
b.push_back(p);
}
void dfs(int k, int p)
{
int copii = 0;
viz[k] = 1;
timp[k] = low[k] = ++ct;
for(int i = 0; i < v[k].size(); i ++)
{
if(viz[v[k][i]] == 0)
{
q.push_back({k, v[k][i]});
copii ++;
dfs(v[k][i], k);
low[k] = min(low[k], low[v[k][i]]);
if(timp[k] <= low[v[k][i]])
new_bix(k, v[k][i]);
}
else if(v[k][i] != p)
low[k] = min(low[k], timp[v[k][i]]);
}
}
int main()
{
int n, m;
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> n >> m;
for(int i = 1; i <= m; i ++)
{
int x, y;
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i = 1; i <= n; i ++)
if(viz[i] == 0)
q.clear(), dfs(i, -1);
g << b.size() << "\n";
for(int i = 0; i < b.size(); i ++)
{
for(int j = 0; j < b[i].size(); j ++)
g << b[i][j] << " ";
g << "\n";
}
return 0;
}