Pagini recente » Cod sursa (job #3315415) | Cod sursa (job #3307694) | Cod sursa (job #3319798) | Cod sursa (job #3314007) | Cod sursa (job #3314029)
#include <fstream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
const string file = "biconex";
#define fileIn file + ".in"
#define fileOut file + ".out"
int n, m;
vector<vector<int>> G;
void reading(){
ifstream fin(fileIn);
fin >> n >> m;
G.resize(n + 1);
int x, y;
for(int i = 1; i <= m; i++){
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
const int nMax = 1e5 + 5;
int parent[nMax], dis[nMax], low[nMax], globalTime;
vector<vector<int>> comp;
stack<pair<int, int>> s;
void getGroup(int x, int y){
vector<int> nodes;
int topX, topY;
do{
topX = s.top().first;
topY = s.top().second;
s.pop();
nodes.push_back(topX);
nodes.push_back(topY);
}while(topX != x || topY != y);
comp.push_back(nodes);
}
void dfs(int node){
dis[node] = low[node] = ++globalTime;
for(int child: G[node]){
if(parent[node] == child) continue;
if(dis[child] == 0){
parent[child] = node;
s.push({node, child});
dfs(child);
low[node] = min(low[node], low[child]);
if(low[child] >= dis[node])
getGroup(node, child);
}else
low[node] = min(low[node], low[child]);
}
}
vector<int> getUniqueValues(vector<int> v){
if(v.empty()) return v;
sort(v.begin(), v.end());
vector<int> aux;
aux.push_back(v[0]);
for(int i = 1; i < v.size(); i++)
if(v[i] != v[i - 1]) aux.push_back(v[i]);
return aux;
}
int main(){
reading();
for(int i = 1; i <= n; i++)
if(dis[i] == 0)dfs(i);
for(int i = 0; i < comp.size(); i++)
comp[i] = getUniqueValues(comp[i]);
ofstream fout(fileOut);
fout << comp.size() << '\n';
for(auto &v: comp){
for(int x: v)
fout << x << ' ';
fout << '\n';
}
}