Pagini recente » Cod sursa (job #1476454) | Cod sursa (job #1677016) | Cod sursa (job #364521) | Cod sursa (job #260823) | Cod sursa (job #1095651)
// 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>
#define Nmax 100099
#define NIL -1
#define x first
#define y second
#define mp make_pair
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;
stack < edge > st;
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)
{
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);
// Check if the subtree rooted with *it has a connection to one of the ancestors of node
if(low[*it]<low[node])low[node]=low[*it];
// node is an articulation point in following cases
// (1) node is root of DFS tree and has two or more chilren.
if (T[node]==NIL && children>1)
{ cutPoint[node]=1;
edge M;
do
{
M=st.top(); st.pop();
g<<M.x<<' '<<M.y<<' ';
}while(M!=edge(node,*it));
g<<'\n';
}
// (2) If node is not root and low value of one of its child is more
// than discovery value of node.
if(T[node]!=NIL && low[*it]>found[node])cutPoint[node]=1;
if(T[node]!=NIL && low[*it]>=found[node])
{
cutPoint[node]=1;
edge M;
do
{
M=st.top(); st.pop();
g<<M.x<<' '<<M.y<<' ';
}while(M!=edge(node,*it));
g<<'\n';
}
}
// Update low value of node for parent function calls.
else
if(*it!=T[node] && found[*it]<low[node])low[node]=found[*it];
}
void Tarjan(),ReadInput();
int main()
{
ReadInput();
Tarjan();
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);
//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);
}
}