Pagini recente » Cod sursa (job #179102) | Cod sursa (job #2879523) | Cod sursa (job #1345400) | Cod sursa (job #1753388) | Cod sursa (job #2791863)
#include <bits/stdc++.h>
#include <iostream>
#define N 100010
using namespace std;
ifstream input("biconex.in");
ofstream output("biconex.out");
stack<pair<int, int>> component_node;
bool visited[N];
int level[N];
int low_level[N];
vector<int> adj[N];
vector<int> bcc[N];
int current;
void DFS(int node, int parent)
{
visited[node] = 1;
level[node] = level[parent] + 1;
low_level[node] = level[node];
int child;
int dim = adj[node].size();
for ( int i = 0; i< dim ; i++)
{
child = adj[node][i];
if (child != parent)
{
if (visited[child] == true) //daca fiul sau a fost deja parcurs si nu este tatal nodului curent, muchia (fiu,nod) este muchie de intoarcere
{
//cout<<"true "<<node<<" "<<*iter<<" "<<level[*iter]<<"\n";
if(level[child] < low_level[node])low_level[node] = level[child]; //actualizam valoarea low_level[nod] daca fiul sau se afla mai sus decat el (p[t ca avem muchie de intoarcere
}
else //daca fiul sau nu a fost inca parcurs, continuam DFS din fiu
{
component_node.push({node, child});
//cout<<"inainte de dfs"<<node<<" "<<*iter<<" "<<level[*iter]<<"\n";
DFS(child, node);
//cout<<"dupa dfs"<<*iter<<" "<<level[*iter]<<"\n";
if (low_level[child] < low_level[node])
low_level[node] = low_level[child]; //daca la intoarcerea din apel fiul are un nivel de intoarcere mai mic decat al nodului, actualizam low_level[node]
if (low_level[child] >= level[node])
{
while( component_node.top().first != node)
{
bcc[current].push_back(component_node.top().second);
component_node.pop();
}
bcc[current].push_back(component_node.top().second);
bcc[current].push_back(component_node.top().first);
component_node.pop();
current++;
// cout << current;
}
}
}
}
}
int main() {
// insert code here...
int no_nodes, no_edges;
int x, y;
input >> no_nodes >> no_edges;
for(int i = 1; i <= no_edges; ++i)
{
input >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
DFS(1, 0);
output <<current<<"\n";
for (int i =0 ; i <= current; i++)
{
for (int j = bcc[i].size(); j >= 0; j--)
if(bcc[i][j])
output<<bcc[i][j]<< " ";
output<<"\n";
}
return 0;
}