Pagini recente » Cod sursa (job #3138627) | Cod sursa (job #601805)
Cod sursa(job #601805)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
#define nmax 100010
#define pb push_back
struct edge{
int x,y;};
stack<edge> S;
int N,M;
vector<int> G[nmax];
int h=0;
int low[nmax],def[nmax];
ofstream fout("biconex.out");
vector<vector<int> > comp;
void extrage(int x,int y)
{
edge dummy;
vector<int> con;
do
{
dummy=S.top();
S.pop();
con.pb(dummy.x);
con.pb(dummy.y);
}
while(x!=dummy.x || y!=dummy.y);
comp.pb(con);
}
void dfs(int x,int t)
{
h++;
def[x]=h;
low[x]=h;
int y;
vector<int>::iterator it;
for(it=G[x].begin();it<G[x].end();it++)
{
y=*it;
if(y!=t)
{
if(def[y]==0) //muchie de arbore
{
S.push((edge){x,y});
dfs(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=def[x])
{
extrage(x,y);
}
}
else if(def[x]>def[y]) //daca x->y e muchie inainte, nu muchie de inaintare
{
S.push((edge){x,y});
low[x]=min(low[x],niv[y]);
}
}
}
}
void cit()
{
int i,x,y;
ifstream fin("biconex.in");
fin>>N>>M;
for(i=1;i<=M;i++)
{
fin>>x>>y;
G[x].pb(y);
G[y].pb(x);
}
fin.close();
}
int main()
{
cit();
dfs(1,0);
vector<vector<int> >::iterator it;
vector<int>::iterator jt;
fout<<comp.size()<<"\n";
for(it=comp.begin();it<comp.end();it++)
{
sort(it->begin(),it->end());
(*it).erase(unique(it->begin(),it->end()),it->end());
for(jt=it->begin();jt<it->end();jt++)
{
fout<<*jt<<" ";
}
fout<<"\n";
}
fout.close();
return 0;
}