Pagini recente » Cod sursa (job #1975353) | Cod sursa (job #3134377) | Cod sursa (job #2591136) | Cod sursa (job #2301357) | Cod sursa (job #1095695)
// 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 <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],CutVertex;
typedef pair<int,int> edge;
stack < edge > st;
vector < vector < int > > BCC;
vector <edge>CriticalEdge;
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 > 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);
BCC.pb(newcomp);
}
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]==NIL)
{
++children , T[*it]=node, st.push(edge(node,*it));
DFS(*it);
low[node]=min(low[node],low[*it]);
if (T[node]==NIL && children>1) //e radacina arborelui DFS
{
CutVertex.pb(node);
ExtractBCC(edge(node,*it));
CriticalEdge.pb(edge(node,*it));
}
if(T[node]!=NIL && low[*it]>=found[node])
{
CutVertex.pb(node);
ExtractBCC(edge(node,*it));
if(low[*it]>found[node])CriticalEdge.pb(edge(node,*it));
}
}
else
if(*it!=T[node] && found[*it]<low[node])low[node]=found[*it];
}
void Tarjan(),PrintBiconnectedComponents(),PrintCriticalEdges(),PrintCriticalNodes(),ReadInput();
int main()
{
ReadInput();
Tarjan();
//PrintCriticalNodes();
//PrintCriticalEdges();
PrintBiconnectedComponents();
return 0;
}
void Tarjan()
{
for (int i=1; i<=N;++i)T[i]=NIL;
for (int i=1; i<=N;++i)
if (T[i]==NIL)
{
T[i]=i;
DFS(i);
}
}
void PrintBiconnectedComponents()
{
//ExtractBCC(edge(0,0));
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 PrintCriticalEdges()
{
EliminateDuplicates(CriticalEdge);
g<<CriticalEdge.size()<<'\n';
for(vector<edge>::iterator it=CriticalEdge.begin();it!=CriticalEdge.end();++it)
g<<it->x<<' '<<it->y<<'\n';
}
void PrintCriticalNodes()
{
EliminateDuplicates(CutVertex);
g<<CutVertex.size()<<'\n';
for(vector<int>::iterator it=CutVertex.begin();it!=CutVertex.end();++it)
g<<*it<<' ';
g<<'\n';
}
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);
}
}