#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pdi pair<double, int>
#define pcc pair<char, char>
#define tiii tuple<int, int, int>
#define tlii tuple<int, int, int>
#define tl tuple<ll, ll, ll, ll>
#define tls tuple<ll, ll, ll>
#define INF numeric_limits<ll>::max()/2
#define MOD 1000000007
#define MIO 1000000
#define mp make_pair
#include <bits/stdc++.h>
using namespace std;
/*void hierholzer(int i, vector<vector<pii>>& adjlist, vector<vector<bool>>& active, vector<int>& output)
{
for(int k = 0; k < (int) adjlist[i].size(); k++)
{
if(active[i][k])
{
int j = adjlist[i][k].first;
int ind = adjlist[i][k].second;
active[i][k] = false;
active[j][ind] = false;
hierholzer(j, adjlist, active, output);
output.push_back(j);
}
}
}*/
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin>>n>>m;
vector<vector<pii>> adjlist(n, vector<pii> (0));
vector<vector<bool>> active(n, vector<bool> (0));
for(int i = 0; i < m; i++)
{
int a, b;
cin>>a>>b;
a--; b--;
adjlist[a].push_back({b, adjlist[b].size()});
adjlist[b].push_back({a, adjlist[a].size()-1});
}
for(int i = 0; i < n; i++)
{
active[i].assign(adjlist[i].size(), true);
}
vector<int> output(0);
vector<int> ind(n, 0);
stack<int> hierholzer;
hierholzer.push(0);
while(hierholzer.size())
{
int u = hierholzer.top();
int index = ind[u];
while(index < (int) adjlist[u].size() && !active[u][index])
{
index++;
}
ind[u] = index+1;
if(index >= (int) adjlist[u].size())
{
hierholzer.pop();
output.push_back(u);
}
else
{
hierholzer.push(adjlist[u][index].first);
active[u][index] = false;
active[adjlist[u][index].first][adjlist[u][index].second] = false;
}
}
//output.push_back(0);
//reverse(output.begin(), output.end());
/*for(int i : output)
{
cout<<i+1<<" ";
}
cout<<"\n";*/
stack<int> tour;
vector<bool> instack(n, false);
for(int i : output)
{
if(instack[i])
{
vector<int> senior(0);
int v = -1;
while(v != i)
{
v = tour.top();
tour.pop();
instack[v] = false;
senior.push_back(v);
}
tour.push(i);
instack[i] = true;
for(int j : senior)
{
cout<<j+1<<" ";
}
cout<<"\n";
}
else
{
tour.push(i);
instack[i] = true;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
6 ms |
1108 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
28 ms |
3624 KB |
Output is correct |
10 |
Correct |
2 ms |
588 KB |
Output is correct |
11 |
Correct |
2 ms |
592 KB |
Output is correct |
12 |
Correct |
31 ms |
4000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
5 ms |
1100 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
29 ms |
3552 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
596 KB |
Output is correct |
12 |
Correct |
32 ms |
4088 KB |
Output is correct |
13 |
Correct |
55 ms |
15228 KB |
Output is correct |
14 |
Correct |
54 ms |
11756 KB |
Output is correct |
15 |
Correct |
56 ms |
11376 KB |
Output is correct |
16 |
Correct |
54 ms |
16328 KB |
Output is correct |
17 |
Correct |
60 ms |
11840 KB |
Output is correct |
18 |
Correct |
56 ms |
12916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
5 ms |
1108 KB |
Output is correct |
8 |
Correct |
2 ms |
596 KB |
Output is correct |
9 |
Correct |
28 ms |
3600 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
31 ms |
4024 KB |
Output is correct |
13 |
Correct |
56 ms |
15292 KB |
Output is correct |
14 |
Correct |
52 ms |
11732 KB |
Output is correct |
15 |
Correct |
59 ms |
11396 KB |
Output is correct |
16 |
Correct |
54 ms |
16296 KB |
Output is correct |
17 |
Correct |
59 ms |
11852 KB |
Output is correct |
18 |
Correct |
53 ms |
12956 KB |
Output is correct |
19 |
Correct |
392 ms |
80708 KB |
Output is correct |
20 |
Correct |
422 ms |
63420 KB |
Output is correct |
21 |
Correct |
377 ms |
59828 KB |
Output is correct |
22 |
Correct |
395 ms |
80648 KB |
Output is correct |
23 |
Correct |
142 ms |
18424 KB |
Output is correct |
24 |
Correct |
434 ms |
58592 KB |
Output is correct |
25 |
Correct |
373 ms |
64328 KB |
Output is correct |