Pagini recente » Cod sursa (job #2250686) | Cod sursa (job #2987265) | Cod sursa (job #2611293) | Cod sursa (job #481013) | Cod sursa (job #1166355)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define Nmax 100009
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
typedef pair<int,int> PP;
int N,M,x,y,low[Nmax],found[Nmax],order,T[Nmax];
vector < int > G[Nmax],CV;
vector < PP > CE;
vector < vector < int > > BCC;
stack < PP > st;
template < class T >
inline void MakeUnique(vector < T > &v)
{
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()) ,v.end());
}
inline void GetBCC(PP E)
{
vector < int > v;
PP aux;
do
{
aux=st.top() , st.pop();
v.pb(aux.x) , v.pb(aux.y);
}while(aux!=E);
BCC.pb(v);
}
inline void DFS(int node)
{
int children=0;
found[node]=low[node]=++order;
for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
if(!T[*it])
{
++children , T[*it]=node , st.push(PP(node,*it));
DFS(*it);
if(T[node]==node && children>1)CV.pb(node);
if(T[node]!=node && low[*it]>=found[node])CV.pb(node);
if(low[*it]>=found[node])GetBCC(PP(node,*it));
if(low[*it]>found[node]) CE.pb(PP(node,*it));
}
else if(*it!=T[node])low[node]=min(low[node],found[*it]);
}
int main()
{
f>>N>>M;
for(int i=1;i<=M;++i)
f>>x>>y , G[x].pb(y) , G[y].pb(x);
for(int i=1;i<=N;++i)
if(!T[i]) T[i]=i , DFS(i);
MakeUnique(CV);
MakeUnique(CE);
g<<BCC.size()<<'\n';
for(int i=0;i<BCC.size();++i)
{
//g<<BCC[i].size()<<' ';
for(vector<int>::iterator it=BCC[i].begin();it!=BCC[i].end();++it)
g<<*it<<' ';
g<<'\n';
}
return 0;
}