Pagini recente » Statisticile problemei Street Crypto | Cod sursa (job #2507350) | Cod sursa (job #2052387) | Rating Narcis Necula (narcios_necula) | Cod sursa (job #937128)
Cod sursa(job #937128)
#include <set>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
using namespace std;
typedef pair<int, int> pr;
const int NMAX = 100011;
int idx, countBC;
int dfsIdx[NMAX], lowIdx[NMAX];
vector<pr> Stack;
vector<int> G[NMAX];
set<int> BC[NMAX];
inline int min(int x, int y) {return x <= y ? x : y;}
inline void DFS(int x)
{
dfsIdx[x] = lowIdx[x] = ++idx;
vector<int>::iterator it = G[x].begin(), iend = G[x].end();
for(; it < iend; ++it)
{
if(!dfsIdx[*it])
{
Stack.push_back(pr(x, *it));
DFS(*it);
lowIdx[x] = min(lowIdx[x], lowIdx[*it]);
if(lowIdx[*it] >= dfsIdx[x])
{
pr z, y(x, *it);
do {
z = Stack.back(); Stack.pop_back();
BC[countBC].insert(z.first);
BC[countBC].insert(z.second);
}while(y != z);
++countBC;
}
}
else lowIdx[x] = min(lowIdx[x], dfsIdx[*it]);
}
}
int main()
{
int N, M, x, y, i;
ifstream in("biconex.in");
ofstream out("biconex.out");
for(in >> N >> M; M; --M)
{
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(i = 1; i <= N; ++i)
{
if(!dfsIdx[i])
{
DFS(i);
}
}
out << countBC << '\n';
for(i = 0; i < countBC; ++i)
{
copy(BC[i].begin(), BC[i].end(), ostream_iterator<int>(out, " "));
out << '\n';
}
return EXIT_SUCCESS;
}