Pagini recente » Cod sursa (job #2322489) | Cod sursa (job #207461) | Cod sursa (job #1353985) | Cod sursa (job #1715659) | Cod sursa (job #1331892)
#include<stdio.h>
#include<vector>
#include<stack>
#include<utility>
#include<algorithm>
#include<set>
using namespace std;
FILE *in, *out;
//definitions
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
//constants
const int Nmax = (int)1e5+1;
//variables
int nodes, edges;
int node1, node2;
int dfn[Nmax], low[Nmax];
int num;
vector<int> graph[Nmax];
vector<set<int> > answer;
stack<pii> sol;
//functions
void dfs(int node, int father);
void biconex( pii stop);
int main(void)
{
in = fopen("biconex.in", "rt");
out = fopen("biconex.out", "wt");
fscanf(in, "%d%d", &nodes, &edges);
while(edges--)
{
fscanf(in, "%d%d", &node1, &node2);
graph[node1].pb(node2);
graph[node2].pb(node1);
}
for(int i=1; i<=nodes; ++i)
dfn[i] = low[i] = -1;
dfs(3,-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)
{
dfn[node] = low[node] = ++num;
vector<int> :: iterator it, end=graph[node].end();
for( it=graph[node].begin(); it!=end; ++it)
{
if(*it != father && dfn[*it] < dfn[node])
sol.push(mp(node,*it));
if(dfn[*it] == -1)
{
dfs(*it, node);
low[node] = min(low[node], low[*it]);
if(low[*it] >= dfn[node])
biconex(mp(node,*it));
}
else
{
if(*it!=father)
low[node] = min(low[node], dfn[*it]);
}
}
}
void biconex(pii stop)
{
set<int> temp;
pii curent;
do
{
curent = sol.top();
sol.pop();
temp.insert(curent.first);
temp.insert(curent.second);
}
while(curent!=stop);
answer.pb(temp);
temp.clear();
}