Pagini recente » Cod sursa (job #787385) | Cod sursa (job #714706) | Cod sursa (job #307247) | Cod sursa (job #2048922) | Cod sursa (job #869344)
Cod sursa(job #869344)
// Include
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
// Definitii
#define pb push_back
#define mp make_pair
#define edge pair<int, int>
#define from first
#define to second
// Constante
const int sz = (int)1e5+1;
// Functii
void dfs(int node, int father, int level);
void biconex(int currentFrom, int currentTo);
// Variabile
ifstream in("biconex.in");
ofstream out("biconex.out");
int nodes, edges;
int depth[sz], lowLevel[sz];
vector<int> graph[sz];
stack<edge> edgesStack;
vector<set<int> > answer;
// Main
int main()
{
in >> nodes >> edges;
int rFrom, rTo;
for(int i=1 ; i<=edges ; ++i)
{
in >> rFrom >> rTo;
graph[rFrom].pb(rTo);
graph[rTo].pb(rFrom);
}
dfs(1, -1, 1);
out << answer.size() << '\n';
vector<set<int> >::iterator it, end=answer.end();
for(it=answer.begin() ; it!=end ; ++it)
{
set<int> current = *it;
set<int>::iterator sit, send=current.end();
for(sit=current.begin() ; sit!=send ; ++sit)
out << *sit << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}
void dfs(int node, int father, int level)
{
depth[node] = level;
lowLevel[node] = level;
vector<int>::iterator it, end=graph[node].end();
for(it=graph[node].begin(); it!=end ; ++it)
{
if(*it == father)
continue;
if(depth[*it])
{
lowLevel[node] = min(lowLevel[node], lowLevel[*it]);
continue;
}
edgesStack.push(mp(node, *it));
dfs(*it, node, level+1);
lowLevel[node] = min(lowLevel[node], lowLevel[*it]);
if(level <= lowLevel[*it])
biconex(node, *it);
}
}
void biconex(int currentFrom, int currentTo)
{
set<int> elements;
edge current;
do
{
current = edgesStack.top();
edgesStack.pop();
elements.insert(current.from);
elements.insert(current.to);
} while(current.from != currentFrom && current.to != currentTo);
answer.pb(elements);
elements.clear();
}