Pagini recente » Cod sursa (job #1617999) | Cod sursa (job #2842929) | Cod sursa (job #1535385) | Cod sursa (job #1651798) | Cod sursa (job #2791889)
//
// main.cpp
// Componente biconexe
//
// Created by Mara Dascalu on 30/10/2021.
//
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
using namespace std;
ifstream input("biconex.in");
ofstream output("biconex.out");
//class Edge{
//public:
// int u;
// int v;
// Edge(int u, int v){
// this->u = u;
// this->v = v;
// }
//};
class Graph
{
int nodes, edges;
vector<int> adj[100010];
int cost[1001];
queue<int> queue_bfs;
list<int>:: iterator iter;
int level[100010] = {0};
int low_level[100010] = {0};
stack<pair<int, int>> component_node;
public:
bool visited[100010] = {0};
vector<int> bcc[100010]; //vectorul care stocheaza componentele biconexe
int current = 0;
void set_no_nodes(int n) {nodes = n;}
int get_no_nodes() {return nodes;}
void set_no_edges(int n) {edges = n;}
int get_no_edges() {return edges;}
void addEdge_dg (int a, int b)
{
adj[a].push_back(b);
}
void addEdge_ug (int a, int b)
{
adj[a].push_back(b);
// adj[a].sort();
adj[b].push_back(a);
// adj[b].sort();
}
/*
void DFS(int node)
{
visited[node] = 1;
//output<<node<<" ";
for (iter = adj[node].begin(); iter != adj[node].end(); iter++)
if( !visited[*iter])
DFS(*iter);
}
void afis_adj(int node){
list<int> :: iterator i;
for(i = adj[node].begin(); i != adj[node].end(); i++)
cout<<*i<<" ";
}
void BFS (int node)
{
memset(cost, -1, sizeof(cost));
visited[node] = 1; //marchez nodul curent ca vizitat
queue_bfs.push(node);
cost[node] = 0;
while (!queue_bfs.empty()) {
node = queue_bfs.front(); //iau nodul din varful cozii
queue_bfs.pop();
for (iter = adj[node].begin(); iter != adj[node].end(); iter++) //parcurg toti vecinii sai
if ( !visited[*iter]) //daca sunt nevizitati
{
visited[*iter] = 1; //ii marchez ca vizitati
queue_bfs.push(*iter); //ii adaug in coada
cost[*iter] = cost[node] + 1; //calculez costul raportat la "parintele" sau
}
}
}
void out_cost (int no)
{
for (int i = 1; i <= no; i++)
output<<cost[i]<<" ";
}
*/
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();
//bcc[current].push_back(node);
current++;
}
}
}
}
}
}g;
int main(int argc, const char * argv[]) {
int no_nodes, no_edges, n1, n2;
input>>no_nodes>>no_edges;
for (int i = 0 ; i < no_edges; i++)
{
input>>n1>>n2;
g.addEdge_ug(n1, n2);
}
g.DFS(1, 0);
output<< g.current << "\n";
for (int i =0 ; i <= g.current; i++)
{
for (int j = g.bcc[i].size() - 1; j >= 0; j--)
if(g.bcc[i][j])
output<<g.bcc[i][j]<<" ";
output<<"\n";
}
return 0;
}