Pagini recente » Cod sursa (job #1908491) | Cod sursa (job #1320921) | Cod sursa (job #2628461) | Autentificare | Cod sursa (job #3003871)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
vector <int> g[N];
pair <int, int> dist[N];
int parent[N];
bool verif[N];
bool used[N];
int k = 0, ans = 1;
ifstream in("biconex.in");
ofstream out("biconex.out");
stack <pair<int, int>> muchii;
void afis(pair <int, int> muchie)
{
set <int> sol;
while(!muchii.empty())
{
pair<int, int> aux = muchii.top();
sol.insert(aux.first);
sol.insert(aux.second);
if(aux == muchie)
{
muchii.pop();
break;
}
muchii.pop();
}
for(auto it : sol)
out << it << " ";
out << '\n';
}
void dfs_noprint(int node)
{
verif[node] = 1;
int copii = 0;
dist[++k].first = k;
dist[k].second = k;
for(auto next : g[node])
{
pair <int, int> muchie = {node, next};
if(!verif[next])
{
copii ++;
parent[next] = node;
muchii.push(muchie);
dfs_noprint(next);
dist[node].second = min(dist[node].second, dist[next].second);
if(!parent[node] and copii > 1)
{
ans ++;
// afis(muchie);
}
if(parent[node] and dist[next].second >= dist[node].first)
{
ans ++;
// afis(muchie);
}
}
else if(parent[node] != next and dist[next].first < dist[node].second)
{
dist[node].second = dist[next].first;
muchii.push(muchie);
}
}
}
void dfs(int node)
{
verif[node] = 1;
int copii = 0;
dist[++k].first = k;
dist[k].second = k;
for(auto next : g[node])
{
pair <int, int> muchie = {node, next};
if(!verif[next])
{
copii ++;
parent[next] = node;
muchii.push(muchie);
dfs(next);
dist[node].second = min(dist[node].second, dist[next].second);
if(!parent[node] and copii > 1)
{
ans ++;
afis(muchie);
}
if(parent[node] and dist[next].second >= dist[node].first)
{
ans ++;
afis(muchie);
}
}
else if(parent[node] != next and dist[next].first < dist[node].second)
{
dist[node].second = dist[next].first;
muchii.push(muchie);
}
}
}
int n;
void print_biconnected_component()
{
set <int> sol;
for(int i=1; i<=n; i++)
{
if(!used[i])
{
dfs(i);
while(!muchii.empty())
{
pair <int , int> aux = muchii.top();
sol.insert(aux.first);
sol.insert(aux.second);
muchii.pop();
}
}
}
for(auto it : sol)
out << it << " ";
}
int main()
{
int m;
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs_noprint(1);
out << ans << '\n';
memset(verif, 0, N);
while(!muchii.empty())
muchii.pop();
print_biconnected_component();
return 0;
}