Pagini recente » Cod sursa (job #179120) | Cod sursa (job #3032259) | Cod sursa (job #2046563) | Cod sursa (job #1816495) | Cod sursa (job #575814)
Cod sursa(job #575814)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <set>
using namespace std;
#define N 100000
#define M 200000
vector<int> g[N];
stack<pair<int, int> > sm;
int n, m;
int desc[N], low[N];
int t = 0;
int ncbc = 0;
set<int> cbc[M];
ofstream fo("biconex.out");
void citeste()
{
ifstream fi("biconex.in");
fi >> n >> m;
int x, y;
for(int i = 0; i < m; ++i)
{
fi >> x >> y;
x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
fi.close();
}
void dfs(int v, int tata)
{
desc[v] = t; // timp de descoperire
low[v] = t; // lowest desc
t++;
for(vector<int> :: iterator it = g[v].begin(); it != g[v].end(); ++it)
{
int u = *it;
if(tata == u) continue;
if(desc[u] < 0)
{
sm.push(pair<int, int>(v, u));
dfs(u, v);
if(low[v] > low[u]) low[v] = low[u];
if(low[u] >= desc[v])
{
while(1)
{
pair<int, int> arc = sm.top();
sm.pop();
// cout << (arc.first + 1) << (arc.second + 1) << " ";
cbc[ncbc].insert(arc.first);
cbc[ncbc].insert(arc.second);
if(arc == pair<int, int>(v, u))
{
ncbc++;
// cout << endl;
break;
}
}
}
}
else
{
if(low[v] > desc[u]) low[v] = desc[u];
}
}
}
int main()
{
citeste();
for(int i = 0; i < n; ++i) desc[i] = -1;
dfs(0, -1);
fo << ncbc << endl;
for(int i = 0; i < ncbc; ++i)
{
for(set<int> :: iterator it = cbc[i].begin(); it != cbc[i].end(); ++it)
fo << ((*it) + 1) << " ";
fo << endl;
}
fo.close();
return 0;
}