Pagini recente » Cod sursa (job #611511) | Cod sursa (job #1355607) | Cod sursa (job #1764449) | Cod sursa (job #2816947) | Cod sursa (job #1166181)
// Tarjan - O(N+M)
// CutVertex+CriticalEdges+BCC
#include <fstream>
#include <algorithm>
#include <vector>
#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,x,y,order,found[Nmax],low[Nmax],T[Nmax];
vector< int > G[Nmax];
vector < int> CV; //CutVertex
vector < edge > CE; // CriticalEdges
stack < edge > st;
vector < vector < int > > BCC;
void ReadInput(),PrintCV(),PrintCE(),PrintBCC();
void GetBCC(edge M);
template < class T>
inline void EliminateDuplicates(vector < T > &v)
{
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
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])
CE.pb(edge(node,*it));
if(low[*it]>=found[node])
{
CV.pb(node);
GetBCC(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);
EliminateDuplicates(CV);
EliminateDuplicates(CE);
}
int main()
{
ReadInput();
Tarjan();
//PrintCV();
//PrintCE();
PrintBCC();
f.close();g.close();
return 0;
}
void ReadInput()
{
f>>N>>M;
for(int i=1;i<=M;++i)
f>>x>>y , G[x].pb(y) , G[y].pb(x);
}
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 PrintCV()
{
g<<CV.size()<<'\n';
for(vector<int>::iterator it=CV.begin();it!=CV.end();++it)
g<<*it<<' ';
g<<'\n';
}
void PrintCE()
{
g<<CE.size()<<'\n';
for(vector<edge>::iterator it=CE.begin();it!=CE.end();++it)
g<<it->x<<' '<<it->y<<'\n';
}
void PrintBCC()
{
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';
}
}