Pagini recente » Cod sursa (job #693632) | Cod sursa (job #1495661) | Cod sursa (job #24583) | Cod sursa (job #1247227) | Cod sursa (job #2793146)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
class graph{
int n, ct;
vector < vector < int > > G, ReverseG, sol;
queue < int > Bfs;
stack < int > Ctc, Topo, Biconex;
vector < bool > vis, vis2;
vector < int > level, low;
void bfs(int source)
{
vector < int > nodes;
nodes.resize(n + 1, -1);
Bfs.push(source); nodes[source] = 0;
while(!Bfs.empty())
{
int node = Bfs.front();
Bfs.pop();
for(int i = 0; i < G[node].size(); ++i)
{
int nnode = G[node][i];
if(nodes[nnode] == -1)
{
nodes[nnode] = nodes[node] + 1;
Bfs.push(nnode);
}
}
}
for(int i = 1; i <= n; ++i)
out << nodes[i] << " ";
}
void dfs(int node)
{
vis[node] = 1;
for(int i = 0; i < G[node].size(); ++i)
{
int nnode = G[node][i];
if(vis[nnode] == 0)
dfs(nnode);
}
}
void dfs_ctc_1(int node)
{
vis[node] = 1;
for(int i = 0; i < G[node].size(); ++i)
{
int nnode = G[node][i];
if(vis[nnode] == 0)
dfs_ctc_1(nnode);
}
Ctc.push(node);
}
void dfs_ctc_2(int node)
{
vis2[node] = 1;
sol[ct - 1].push_back(node);
for(int i = 0; i < ReverseG[node].size(); ++i)
{
int nnode = ReverseG[node][i];
if(vis2[nnode] == 0)
dfs_ctc_2(nnode);
}
}
void dfs_topo(int node)
{
vis[node] = 1;
for(int i = 0; i < G[node].size(); ++i)
{
int nnode = G[node][i];
if(vis[nnode] == 0)
dfs_topo(nnode);
}
Topo.push(node);
}
void dfs_biconex(int node, int dad)
{
vis[node] = 1;
level[node] = level[dad] + 1;
low[node] = level[node];
for(int i = 0; i < G[node].size(); ++i)
{
int nnode = G[node][i];
if(nnode != dad)
{
if(vis[nnode] == 1)
{
if(level[nnode] < low[node])
low[node] = level[nnode];
}
else
{
Biconex.push(nnode);
dfs_biconex(nnode, node);
if(low[nnode] < low[node])
low[node] = low[nnode];
if(level[node] <= low[nnode])
{
++ct;
Biconex.push(node);
while(!Biconex.empty() && Biconex.top() != nnode)
{
sol[ct - 1].push_back(Biconex.top());
Biconex.pop();
}
if(!Biconex.empty())
{
sol[ct - 1].push_back(Biconex.top());
Biconex.pop();
}
}
}
}
}
}
public:
void solve_bfs()
{
int m, s, x, y;
in >> n >> m >> s;
G.resize(n + 1);
for(int i = 0; i < m; ++i)
{
in >> x >> y;
G[x].push_back(y);
}
bfs(s);
}
void solve_dfs()
{
int m, x, y, ct = 0;
in >> n >> m;
G.resize(n + 1);
vis.resize(n + 1, false);
for(int i = 0; i < m; ++i)
{
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(vis[i] == 0)
{
++ct;
dfs(i);
}
out << ct;
}
void solve_ctc()
{
int m, x, y;
in >> n >> m;
G.resize(n + 1);
ReverseG.resize(n + 1);
sol.resize(n + 1);
vis.resize(n + 1, false);
vis2.resize(n + 1, false);
for(int i = 1; i <= m; ++i)
{
in >> x >> y;
G[x].push_back(y);
ReverseG[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(vis[i] == 0)
dfs_ctc_1(i);
ct = 0;
while(!Ctc.empty())
{
int node = Ctc.top();
Ctc.pop();
if(vis2[node] == 0)
{
++ct;
dfs_ctc_2(node);
}
}
out << ct << "\n";
for(int i = 0; i < ct; ++i)
{
for(int j = 0; j < sol[i].size(); ++j)
out << sol[i][j] << " ";
out << "\n";
}
}
void solve_topo()
{
int m, x, y;
in >> n >> m;
G.resize(n + 1);
vis.resize(n + 1, false);
for(int i = 1; i <= m; ++i)
{
in >> x >> y;
G[x].push_back(y);
}
for(int i = 1; i <= n; ++i)
if(vis[i] == 0)
dfs_topo(i);
while(!Topo.empty())
{
int node = Topo.top();
Topo.pop();
out << node << " ";
}
}
void solve_biconex()
{
int m, x, y;
in >> n >> m;
G.resize(n + 1);
sol.resize(n + 1);
level.resize(n + 1, 0);
low.resize(n + 1, 0);
vis.resize(n + 1, false);
for(int i = 1; i <= m; ++i)
{
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
ct = 0;
dfs_biconex(1, 0);
out << ct << "\n";
for(int i = 0; i < ct; ++i)
{
for(int j = 0; j < sol[i].size(); ++j)
out << sol[i][j] << " ";
out << "\n";
}
}
};
int main()
{
graph G;
G.solve_biconex();
return 0;
}