Pagini recente » Cod sursa (job #1612311) | Cod sursa (job #113186) | Cod sursa (job #2701672) | Cod sursa (job #324823) | Cod sursa (job #2660895)
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
#define MAXN 100005
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector <int> adj[MAXN], con, idx, lowlink, in_stack;
vector < vector <int> > C;
stack < pair <int, int> > S;
int index, n;
void read_in()
{
int cnt_edges, x, y;
cin >> n;
for (cin >> cnt_edges; cnt_edges > 0; -- cnt_edges)
cin >> x >> y,
adj[x].push_back(y),
adj[y].push_back(x);
cin.close();
}
void stiva(const int x, const int y)
{
vector <int> con;
int tx, ty;
do
{
tx = S.top().first, ty = S.top().second;
S.pop();
con.push_back(tx), con.push_back(ty);
}
while (tx != x || ty != y);
C.push_back(con);
}
void DFS(const int n, const int father, int number)
{
idx[n] = lowlink[n] = number;
for(int i = 0 ; i < adj[n].size() ; i++)
{
int u = adj[n][i];
if(u == father) continue ;
if(idx[u] == -1)
{
S.push(make_pair(n, u));
DFS(u, n, number + 1);
lowlink[n] = min(lowlink[n], lowlink[u]);
if(lowlink[u] >= idx[n])
stiva(n, u);
}
else
lowlink[n] = min(lowlink[n], idx[u]);
}
}
void print_out()
{
cout << C.size() << "\n";
for (int i = 0; i < C.size(); ++ i)
{
sort(C[i].begin(), C[i].end());
C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
for (int j = 0; j < C[i].size(); ++ j)
cout << C[i][j] << " ";
cout << "\n";
}
cout.close();
}
int main(void)
{
int n;
read_in();
idx.resize(n), lowlink.resize(n);
idx.assign(n, -1);
DFS(1, 0, 0);
print_out();
return 0;
}