Pagini recente » Cod sursa (job #2885791) | Cod sursa (job #1279919) | Cod sursa (job #2129087) | Cod sursa (job #1194170) | Cod sursa (job #1420545)
// Tarjan - O(N+M)
// cutVertex + criticalEdge + BiconnetedComponets
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define Nmax 100009
#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> PP;
int N, M;
vector<int> G[Nmax];
int low[Nmax], found[Nmax], order, T[Nmax];
vector<int> cutVertex;
vector<PP> criticalEdge;
vector< vector <int> > biconexComponents;
stack<PP> st;
template<class T>
void makeUnique(vector<T> &v){
sort(v.begin(), v.end());
v.erase( unique( v.begin(), v.end() ), v.end());
}
void GetBCC(PP E) {
vector<int> v;
PP aux;
do{
aux = st.top();
st.pop();
v.pb(aux.x);
v.pb(aux.y);
}while(aux != E);
makeUnique(v);
biconexComponents.pb(v);
}
inline void DFS(const 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]){
++children , T[*it]=node , st.push(PP(node,*it));
DFS(*it);
low[node]=min(low[node],low[*it]);
if(T[node] == node && children > 1) cutVertex.pb(node);
if(T[node] != node && low[*it] >= found[node]) cutVertex.pb(node);
if(low[*it] >= found[node]) GetBCC(PP(node,*it));
if(low[*it] > found[node]) criticalEdge.pb(PP(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]) { /* nu are tata <=> nu a mai fost vizitat */
T[i]=i;
DFS(i);
}
makeUnique(cutVertex);
makeUnique(criticalEdge);
}
void ReadInput(), PrintCutVertex(), PrintCriticalEdge(), PrintBiconnectedComponents();
int main()
{
ReadInput();
Tarjan();
//PrintCutVertex();
//PrintCriticalEdge();
PrintBiconnectedComponents();
f.close();g.close();
return 0;
}
void PrintCutVertex() {
g << cutVertex.size() << '\n';
for(vector<int>::iterator it = cutVertex.begin(); it != cutVertex.end(); ++it) {
g << *it << ' ';
}
g<<'\n';
}
void PrintCriticalEdge() {
g << criticalEdge.size() << '\n';
for(vector<PP>::iterator it = criticalEdge.begin(); it != criticalEdge.end(); ++it) {
g<< it->x << ' ' << it->y << '\n';
}
}
void PrintBiconnectedComponents() {
g << biconexComponents.size() << '\n';
for(int i = 0; i < (int)biconexComponents.size(); ++i) {
//g << biconexComponents[i].size() << ' ';
for(vector<int>::iterator it = biconexComponents[i].begin(); it != biconexComponents[i].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].pb(y);
G[y].pb(x);
}
}