Pagini recente » Cod sursa (job #2258189) | Cod sursa (job #3208009) | Cod sursa (job #3221845) | Cod sursa (job #368891) | Cod sursa (job #3228518)
#include <iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
using namespace std;
ifstream in ( "biconex.in" ) ;
ofstream out ( "biconex.out" ) ;
long long times=0;
using ll=long long;
vector<vector<long long>> gr;
vector<long long> tim,fun;//tim - время входа в вершину а fun наим время возврата
vector<long long> col;//col - цвет или номер компоненты вершинной двусвязности
long long maxcolor=0;
vector<bool> painted;
map<pair<long long,long long>,vector<long long>> numedge;
vector<set<ll>> points;
set<long long> key;
void dfs(vector<bool> &used,ll v,ll p=-1){
used[v]=1;
tim[v]=times++;
fun[v]=tim[v];
int child=0;
for (auto u:gr[v])
{
if(u==p){
continue;
}
if(used[u]){
fun[v]=min(fun[v],tim[u]);
}
else{
dfs(used,u,v);
fun[v]= min(fun[v],fun[u]);
child++;
}
}
}
void paint(long long v,long long p=-1){
painted[v]=1;
for (auto u:gr[v])
{
if(u==p){
//обратное ребро к родителю не нужно т.к оно ведет только вверх
continue;
}
if(!painted[u]){
if(fun[u]>=tim[v]){
if(!key.empty())
points.push_back(key);
key=set<long long>();
//setColor(v,u,newcolor);
key.insert(u);
key.insert(v);
paint(u,v);
}else{
//тут нужно ребро vu
//setColor(v,u,color);
key.insert(u);
key.insert(v);
paint(u,v);
}
}
else if(tim[u]<tim[v])
{
//setColor(v,u,color);
key.insert(u);
key.insert(v);
}
}
}
int main(){
long long n,m;
in>>n>>m;
gr=vector<vector<long long>>(n);
tim=vector<long long>(n);
fun=vector<long long>(n);
vector<bool> used= vector<bool>(n,0);
painted=vector<bool>(n);
col=vector<long long>(m);
long long v,u;
for (long long i = 0; i < m; i++)
{
in>>v>>u;
--v;
--u;
gr[v].push_back(u);
gr[u].push_back(v);
numedge[make_pair(min(v,u),max(v,u))].push_back(i);
}
//Первый проход dfs для поиска точек сочленения
for (long long v = 0; v < n; v++)
{
if(!used[v])
dfs(used,v);
}
//Второй проход dfs для окраски графа по компононентам вершн двусвязности
for (long long v = 0; v < n; v++)
{
if(!painted[v]){
paint(v);
}
}
if(!key.empty())
points.push_back(key);
out<<points.size()<<endl;
for (auto i:points)
{
for (auto j:i)
{
out<<j+1<<" ";
out.flush();
}
out<<endl;
}
}