This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
vector<vector<int>> ans;
vector<vector<int>> g(500005); //za svaki cvor pamtimo vector indeksa edge-ova
vector<pii> ed;
bool potrosen[500005]; //da li je edge vec iskoriscen?
vector<int> put;
bool tvis[500005]; //trenutno posecen?
void dfs(int p)
{
if (tvis[p])
{
//for (auto it : put) cout<<it<<" "; cout<<endl;
ans.pb(vector<int>());
while (true)
{
ans.back().pb(put.back());
tvis[put.back()]=false;
put.popb();
if (ans.back().back()==p) break;
}
}
put.pb(p);
tvis[p]=true;
while (!g[p].empty())
{
int ind=g[p].back();
g[p].popb();
if (potrosen[ind]) continue;
potrosen[ind]=true;
auto [u,v]=ed[ind];
if (p==u) dfs(v);
else dfs(u);
}
}
int main()
{
FAST;
int n,m; cin>>n>>m;
ff(i,0,m)
{
int u,v; cin>>u>>v;
ed.pb({u,v});
g[u].pb(i),g[v].pb(i);
}
fff(i,1,n) dfs(i);
/*///validator:
set<pii> uzet;
for (auto it : ans)
{
set<int> dosad;
for (auto jt : it)
{
if (dosad.count(jt)) return cout<<"fatal error",0;
dosad.insert(jt);
}
ff(j,1,(int)it.size())
{
pii sta={min(it[j],it[j-1]),max(it[j],it[j-1])};
if (uzet.count(sta)) return cout<<"mars u picku materinu",0;
uzet.insert(sta);
}
}*/
for (auto it : ans)
{
for (auto jt : it) cout<<jt<<" ";
cout<<"\n";
}
return 0;
}
//Note to self: Check for overflow
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |