Pagini recente » Cod sursa (job #2609296) | Cod sursa (job #1988235) | Cod sursa (job #2339695) | Cod sursa (job #2782627) | Cod sursa (job #2765562)
/*#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define maxi 36000
#define INFINITY 1000000000000
using namespace std;
using int32=int;
using int64=long long int;
using booly=bool;
ifstream f;
ofstream g;
vector<pair<int32,int32>> V[1+maxi];
priority_queue<pair<int64,int64>,vector<pair<int64,int64>>,greater<pair<int64,int64>>> heap;
booly viz[1+maxi];
int64 D[1+maxi];
int32 SURSA[1+maxi],n,m,k;
void INIT(int n)
{
for(int i=1;i<=n;i++)
D[i]=INFINITY;
}
void READ()
{
int a,b,c;
f.open("catun.in",ios::in);
f>>n>>m>>k;
INIT(n);
for(int i=1;i<=k;i++)
f>>a,heap.push(make_pair(0,a)),SURSA[a]=a,D[a]=0;
for(int i=1;i<=m;i++)
{
f>>a>>b>>c;
V[a].push_back(make_pair(b,c));
V[b].push_back(make_pair(a,c));
}
f.close();
return;
}
void DIJKSTRA()
{
while(!heap.empty())
{
int k=heap.top().second;
viz[k]=true;
heap.pop();
for(auto a:V[k])
{
int vecin=a.first;
if(!viz[vecin])
{
if(D[vecin]>D[k]+a.second)
{
D[vecin]=D[k]+a.second;
SURSA[vecin]=SURSA[k];
heap.push(make_pair(D[vecin],vecin));
}
else if(D[vecin]==D[k]+a.second)
{
if(SURSA[k]<SURSA[vecin])
SURSA[vecin]=SURSA[k];
}
}
}
}
return;
}
int main()
{
g.open("catun.out",ios::out);
READ();
DIJKSTRA();
for(int i=1;i<=n;i++)
{
if(i==SURSA[i])
g<<0<<" ";
else g<<SURSA[i]<<" ";
}
g.close();
return 0;
}*/
#include <fstream>
#include <stack>
#include <vector>
#include <unordered_set>
#include <algorithm>
#define maxi 1e+5
using namespace std;
using int32=int;
using booly=bool;
ifstream cin;
ofstream cout;
unordered_set<int> S;
vector<int32> V[1+(int)maxi];
vector<int32> SOL[1+(int)maxi];
vector<int32>::iterator I1,I2;
stack<int32> stiva;
booly viz[1+(int32)maxi];
int32 tata[1+(int32)maxi],lvl[1+(int32)maxi],nma[1+(int32)maxi],n,m,cnt;
void READ()
{
int a,b;
cin.open("biconex.in",ios::in);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
V[a].push_back(b);
V[b].push_back(a);
}
cin.close();
return;
}
void DFS(int x)
{
stiva.push(x);
viz[x]=true;
nma[x]=lvl[x];
for(auto a:V[x])
{
if(viz[a]&&tata[x]!=a)///stramos in app
{
if(lvl[a]<nma[x])
nma[x]=lvl[a];
}
if(!viz[a])
{
tata[a]=x;
lvl[a]=lvl[x]+1;
DFS(a);
if(nma[a]<nma[x])
nma[x]=nma[a];
if(lvl[x]<=nma[a]&&tata[a]==x)
{S.insert(x);
cnt++;
while(stiva.top()!=a)
{
SOL[cnt].push_back(stiva.top());
stiva.pop();
}
SOL[cnt].push_back(a);
stiva.pop();
SOL[cnt].push_back(x);
}
}
}
}
int main()
{
cout.open("biconex.out",ios::out);
READ();
for(int i=1;i<=n;i++)
{
if(!viz[i])
{
lvl[i]=1;
nma[i]=1;
DFS(i);
}
}
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
I1=SOL[i].begin();
I2=SOL[i].end();
sort(I1,I2);
}
for(int i=1;i<=cnt;i++)
{
for(auto a:SOL[i])
cout<<a<<" ";
cout<<'\n';
}
cout.close();
return 0;
}