Pagini recente » Istoria paginii utilizator/madalindobrila | Istoria paginii utilizator/pussy_destroyer | Cod sursa (job #1790988) | Cod sursa (job #2916418) | Cod sursa (job #954751)
Cod sursa(job #954751)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100003
using namespace std;
int N,M,no_components,no;
int num[NMAX],low[NMAX];
vector <int> *graph;
vector <int> solution[NMAX];
pair <int,int> p;
stack <pair <int,int> > st;
ifstream in("biconex.in");
ofstream out("biconex.out");
int min (int x,int y){
if (x<y) return x;
return y;
}
void dfs(int node, int father)
{
int w,x,y;
no++;
num[node]=no;
low[node]=no;
for (vector<int>::iterator it=graph[node].begin();it!=graph[node].end();it++)
{
w=*it;
if (father==node) continue;
if (num[w]==0)
{
st.push(make_pair(node,w));
dfs(w,node);
low[node]=min(low[node],low[w]);
if (low[w]>=num[node])
{
no_components++;
do
{
x=st.top().first;
y=st.top().second;
solution[no_components].push_back(y);
solution[no_components].push_back(x);
st.pop();
}while ((x!=node) && (y!=w));
}
}
else if ((num[w]<num[node])&&(w!=father))
{
st.push(make_pair(node,w));
low[node]=min(low[node],num[w]);
}
}
}
int main()
{
int x,y,i;
in>>N>>M;
graph=new vector<int> [N+1];
for (i=1;i<=M;i++)
{
in>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
no=0;
no_components=0;
for (i=1;i<=N;i++)
num[i]=0;
for (i=1;i<=N;i++)
if (num[i]==0) dfs(i,0);
out<<no_components<<"\n";
for(i=1;i<=no_components;i++)
{
vector<int>::iterator uni;
sort(solution[i].begin(),solution[i].end());
uni=unique(solution[i].begin(),solution[i].end());
solution[i].resize(distance(solution[i].begin(),uni));
for (vector<int>::iterator it=solution[i].begin();it!=solution[i].end();it++)
out<<*it<<" ";
out<<"\n";
}
}