Pagini recente » Cod sursa (job #1483239) | Cod sursa (job #1216971) | Cod sursa (job #1990135) | Cod sursa (job #2811566) | Cod sursa (job #1120768)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define Nmax 100099
#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> edge;
int N,M,order,found[Nmax],low[Nmax],x,y,T[Nmax];
vector < int > G[Nmax],CV;
vector < vector < int > > BCC;
vector < edge > CE;
stack < edge > st;
void ReadInput()
{
f>>N>>M;
for(int i=1;i<=M;++i)
f>>x>>y , G[x].pb(y), G[y].pb(x);
}
template <class T>
inline void EliminateDuplicates(vector < T > &v)
{
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
void GetBCC(edge M)
{
vector < int > newBCC;
edge E;
do
{
E=st.top(); st.pop();
newBCC.pb(E.x); newBCC.pb(E.y);
}while(E!=M);
EliminateDuplicates(newBCC);
BCC.pb(newBCC);
}
void DFS(int node)
{
found[node]=low[node]=++order;
for(vector<int>::iterator it=G[node].begin();it!=G[node].end();++it)
if(!T[*it])
{
T[*it]=node , st.push(edge(node,*it));
DFS(*it);
low[node]=min(low[node],low[*it]);
if(low[*it]>=found[node])
{
CV.pb(node);
GetBCC(edge(node,*it));
}
if(low[*it]>found[node])
CE.pb(edge(node,*it));
}
else
if(*it!=T[node])
low[node]=min(low[node],found[*it]);
}
void Tarjan()
{
for(int i=1;i<=N;++i)
if(!T[i]) T[i]=i,DFS(i);
}
int main()
{
ReadInput();
Tarjan();
g<<BCC.size()<<'\n';
for(int i=0;i<BCC.size();++i,g<<'\n')
for(vector<int>::iterator it=BCC[i].begin();it!=BCC[i].end();++it)
g<<*it<<' ';
g<<'\n';
f.close();g.close();
return 0;
}