Pagini recente » Cod sursa (job #1227391) | Cod sursa (job #40393) | Cod sursa (job #621026) | Cod sursa (job #3001954) | Cod sursa (job #1095759)
// Tarjan - O(N+M)- CutVertex
//low[i] = cea mai mica valoare din subarborele lui i
//found[i] = al catelea nod vizitat este nodul i (ordine cronologica)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100099
#define NIL -1
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream f("biconex.in");ofstream g("biconex.out");
typedef pair<int,int> edge;
int N,T[Nmax],low[Nmax],found[Nmax],order;
vector < int > G[Nmax];
vector < vector < int > > BCC; //componente biconexe
stack < edge > st;
void Tarjan(),ExtractBCC(edge M),PrintBCC(),PrintCE(),PrintCV(),ReadInput();
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]) // nu are tata = nu a fost vizitat sau e radacina DFS
{
++children , T[*it]=node, st.push(edge(node,*it));
DFS(*it);
low[node]=min(low[node],low[*it]);
if (!T[node] && children>1) //e radacina arborelui DFS
ExtractBCC(edge(node,*it));
if(T[node] && low[*it]>=found[node])
ExtractBCC(edge(node,*it));
}
else
if(*it!=T[node])low[node]=min(low[node],found[*it]);
}
int main()
{
ReadInput();
Tarjan();
PrintBCC();
return 0;
}
void Tarjan()
{
for (int i=1; i<=N;++i)
if (!T[i])T[i]=i, DFS(i);
}
template<class T>
inline void EliminateDuplicates(vector<T> &v)
{
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
void ExtractBCC(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 PrintBCC()
{
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<<' ';
}
void ReadInput()
{
int M,x,y;
f>>N>>M;
for(int i=1;i<=M;++i)
f>>x>>y , G[x].pb(y) , G[y].pb(x);
}