Pagini recente » Cod sursa (job #1201557) | Cod sursa (job #2447409) | Cod sursa (job #3236364) | Cod sursa (job #3236929) | Cod sursa (job #2795140)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
class graf{
int noduri, muchii;
vector<vector<int>> adiacenta;
public:
graf(vector<vector<int>> a, int b, int c): adiacenta(a), noduri(b), muchii(c) {};
vector<int> bfs(int start){
vector<int> res(this->adiacenta.size(), -1);
vector<int> vis(this->adiacenta.size());
queue<int> q;
vis[start] = 1;
q.push(start);
res[start] = 0;
while(!q.empty()){
int curr = q.front();
q.pop();
for (int i: adiacenta[curr])
if (vis[i] == 0) {
vis[i] = 1;
q.push(i);
res[i] = res[curr] + 1;
};
}
return res;
}
int dfs(){
vector<int> vis(this->noduri);
int res = 0;
stack<int> s;
for(int i=0; i<this->noduri; i++){
if(vis[i] == 0){
res++;
vis[i]=1;
s.push(i);
while(!s.empty()){
int curr = s.top();
s.pop();
for(int i=adiacenta[curr].size()-1; i>=0; i--){
int nod = adiacenta[curr][i];
if(vis[nod] == 0){
vis[nod] = 1;
s.push(nod);
}
}
}
}
}
return res;
}
void dfsbiconex(int tata, vector<int>& timp, vector<int>& rev, stack<pair<int, int>>& s, int& timpcurent, vector<string>& rasp){
timpcurent++;
timp[tata]=timpcurent;
rev[tata]=timpcurent;
for(int fiu:adiacenta[tata]){
if(timp[fiu]==-1){
s.push(make_pair(tata, fiu));
dfsbiconex(fiu, timp, rev, s, timpcurent, rasp);
rev[tata]=min(rev[tata], rev[fiu]);
if((timp[tata]!=1 && rev[fiu]>=timp[tata]) || (timp[tata]==1 && adiacenta[tata].size()>1)){
pair<int, int> stop = make_pair(tata, fiu);
unordered_set<int> aux;
string str="";
aux.insert(stop.first);
aux.insert(stop.second);
str+=to_string(stop.first);
str+=" ";
str+=to_string(stop.second);
str+=" ";
while(s.top() != stop){
int nodcur = s.top().first;
if(aux.find(nodcur)==aux.end()){
str+=to_string(nodcur);
str+=" ";
aux.insert(s.top().first);
}
s.pop();
}
str+='\n';
rasp.push_back(str);
s.pop();
}
}
else{
rev[tata] = min(rev[tata], timp[fiu]);
if(timp[fiu] < timp[tata]){
s.push(make_pair(tata, fiu));
}
}
}
}
vector<string> biconex(){
vector<int> timp(noduri+1, -1), rev(noduri+1);
stack<pair<int, int>> s;
vector<string> rasp;
int timpo=0;
//pt ca graful nu e neaparat conex trb sa facem de mai multe ori dfs
for(int i=0; i<noduri; i++){
if(timp[i]==-1){
dfsbiconex(i, timp, rev, s, timpo, rasp);
}
if(!s.empty()){
unordered_set<int> aux;
string str;
while(!s.empty()){
if(aux.find(s.top().first)==aux.end()){
aux.insert(s.top().first);
str+=to_string(s.top().first);
str+=" ";
}
if(aux.find(s.top().second)==aux.end()){
aux.insert(s.top().second);
str+=to_string(s.top().second);
str+=" ";
}
s.pop();
}
str+='\n';
rasp.push_back(str);
}
}
return rasp;
}
};
int main(){
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m;
in>>n>>m;
vector<vector<int>> mat(n+1);
for(int i=0; i<m; i++){
int aux1, aux2;
in>>aux1>>aux2;
mat[aux1].push_back(aux2);
mat[aux2].push_back(aux1);
}
graf x(mat, n, m);
vector<string> fin = x.biconex();
out<<fin.size()<<'\n';
for(string i:fin){
out<<i;
}
return 0;
}