Pagini recente » Cod sursa (job #2911301) | Cod sursa (job #2369362) | Cod sursa (job #184875) | Cod sursa (job #2896770) | Cod sursa (job #874403)
Cod sursa(job #874403)
#include <stdio.h>
#include <vector>
#include <stack>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;
//Constante
const int sz = (int)1e5+1;
//Functii
void dfs(int node, int father, int level);
void biconex(pair<int, int> stop);
//Variabile
FILE *in,*out;
int nodes, edges;
int minLevel[sz],depth[sz];
vector <int> graph[sz];
stack <pair<int, int> > st;
vector<set<int> > answer;
int main()
{
in=fopen("biconex.in","rt");
out=fopen("biconex.out","wt");
fscanf(in,"%d%d",&nodes, &edges);
for(int i=1; i<=edges; ++i)
{
int rFrom, rTo;
fscanf(in,"%d%d",&rFrom,&rTo);
graph[rFrom].push_back(rTo);
graph[rTo].push_back(rFrom);
}
dfs(1, -1, 1);
fprintf(out,"%d\n",answer.size());
vector<set<int> >::iterator it, end = answer.end();
for(it=answer.begin(); it!=end; ++it)
{
set<int>::iterator sit, send = it->end();
for(sit=it->begin(); sit!=send; ++sit)
fprintf(out,"%d ",*sit);
fprintf(out,"\n");
}
fclose(in);
fclose(out);
return 0;
}
void dfs(int node, int father, int level)
{
depth[node] = minLevel[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])
{
minLevel[node] = min(minLevel[node], minLevel[*it]);
continue;
}
st.push(make_pair(node, *it));
dfs(*it, node, level+1);
minLevel[node] = min(minLevel[node], minLevel[*it]);
if(level <= minLevel[*it])
biconex(make_pair(node, *it));
}
}
void biconex(pair<int, int> stop)
{
set<int> temp;
pair<int, int> current;
do
{
current = st.top();
st.pop();
temp.insert(current.first);
temp.insert(current.second);
} while(current != stop);
answer.push_back(temp);
temp.clear();
}