Pagini recente » Cod sursa (job #1927012) | Cod sursa (job #2205177) | Cod sursa (job #1099777) | Cod sursa (job #2347117) | Cod sursa (job #1095672)
// Tarjan - O(N+M)- CutVertex
//low[i] = cea mai mica valoare din subarborele lui i
//found[i] = al catelea nod vizitat e i (ordine cronologica)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <algorithm>
#define Nmax 100099
#define NIL -1
#define x first
#define y second
#define mp make_pair
#define pb push_back
using namespace std;
ifstream f("biconex.in");ofstream g("biconex.out");
int N,M,T[Nmax],low[Nmax],found[Nmax],order;
vector < int > G[Nmax],sol[Nmax];
bitset < Nmax > viz,cutPoint;
typedef pair<int,int> edge;
typedef vector < int > Vect;
stack < edge > st;
vector < Vect > ConnectedComponents;
template<class T>
inline void EliminateDuplicates(vector<T> &v)
{
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
void ExtrageComponenta(edge M)
{
Vect newcomp;
edge current;
do
{
if(st.empty())break;
current=st.top(); st.pop();
newcomp.pb(current.x);
newcomp.pb(current.y);
}while(current!=M);
EliminateDuplicates(newcomp);
ConnectedComponents.pb(newcomp);
}
void DFS(int node)
{
int children=0;
viz[node]=1; found[node] = low[node] = ++order;
vector<int>::iterator it;
for (it=G[node].begin();it!=G[node].end();++it)
if (!viz[*it])
{
st.push(edge(node,*it));
++children;
T[*it]=node;
DFS(*it);
if(low[*it]<low[node])low[node]=low[*it];
if (T[node]==NIL && children>1)
{ cutPoint[node]=1;
ExtrageComponenta(edge(node,*it));
}
if(T[node]!=NIL && low[*it]>found[node])cutPoint[node]=1;
if(T[node]!=NIL && low[*it]>=found[node])
{
cutPoint[node]=1;
ExtrageComponenta(edge(node,*it));
}
}
else
if(*it!=T[node] && found[*it]<low[node])low[node]=found[*it];
}
void Tarjan(),ReadInput();
int main()
{
ReadInput();
Tarjan();
g<<ConnectedComponents.size()<<'\n';
for(int i=0;i<ConnectedComponents.size();++i,g<<'\n')
for(vector<int> ::iterator it=ConnectedComponents[i].begin();it!=ConnectedComponents[i].end();++it)
g<<*it<<' ';
return 0;
}
void Tarjan()
{
for (int i=1; i<=N;++i)T[i]=NIL;
for (int i=1; i<=N;++i)
if (!viz[i])DFS(i);
ExtrageComponenta(edge(0,0));
//for (int i =1;i<=N;++i)
//if (cutPoint[i])g<<i<<' ';
}
void ReadInput()
{
f>>N>>M;
for(int i=1;i<=M;++i)
{
int x,y;
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}