Pagini recente » Cod sursa (job #1398673) | Cod sursa (job #1424194) | Cod sursa (job #77831) | Cod sursa (job #719867) | Cod sursa (job #1166383)
#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);
MakeUnique(v);
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);
low[node]=min(low[node],low[*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]);
}
inline void Tarjan()
{
for(int i=1;i<=N;++i)
if(!T[i]) T[i]=i , DFS(i);
MakeUnique(CV);
MakeUnique(CE);
}
inline void PrintCutVertex()
{
g<<CV.size()<<'\n';
for(vector<int>::iterator it=CV.begin();it!=CV.end();++it)
g<<*it<<' ';
g<<'\n';
}
inline void PrintCriticalEdge()
{
g<<CE.size()<<'\n';
for(vector<PP>::iterator it=CE.begin();it!=CE.end();++it)
g<<it->x<<' '<<it->y<<'\n';
}
inline void PrintBiconnectedComponents()
{
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';
}
}
int main()
{
f>>N>>M;
for(int i=1;i<=M;++i)
f>>x>>y , G[x].pb(y) , G[y].pb(x);
Tarjan();
//PrintCutVertex();
//PrintCriticalEdge();
PrintBiconnectedComponents();
f.close();g.close();
return 0;
}