10936 | 2024-04-20 16:40:47 | k_balint | Vasútépítés | cpp17 | Wrong answer 40/100 | 48ms | 12252 KiB |
#include <bits/stdc++.h>
using namespace std;
const int c=1005;
int n,m,tt;
vector<int> adj[c];
int vis[c];
int cnt,deg;
vector<int> kor;
bool van;
int ans[c][c];
int par[c];
bool korben[c];
void dfs(int v){
++cnt; deg+=adj[v].size();
vis[v]=1;
for(int x:adj[v]){
if(!vis[x]) dfs(x);
}
}
void dfs2(int v, int p){
if(van) return;
vis[v]=2, par[v]=p;
for(int x:adj[v]){
if(van) break;
if(x==p) continue;
if(vis[x]==1) dfs2(x,v);
else if(!van){
int k=v;
while(k != par[x]){
kor.push_back(k);
k=par[k];
}
van=1;
}
}
}
void dfs3(int v){
vis[v]=1;
for(int x:adj[v]){
if(!korben[x] && !vis[x]){
ans[v][x]=ans[x][v]=++tt;
dfs3(x);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b; cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
deg=0; cnt=0;
dfs(i);
if(deg>2*cnt){
cout << -1 << endl;
return 0;
}
kor.clear();
van=0;
dfs2(i,0);
for(int j=0;j<kor.size();j++){
int x=kor[(j+1)%kor.size()];
int y=kor[j];
korben[y]=1;
ans[x][y]=ans[y][x]=++tt;
}
}
}
for(int i=1;i<=n;i++) vis[i]=0;
for(int i=1;i<=n;i++){
if(!vis[i] && korben[i]) dfs3(i);
}
for(int i=1;i<=n;i++){
if(!vis[i]) dfs3(i);
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(!ans[i][j]) ans[i][j]=++tt;
cout << ans[i][j] << ' ';
}
cout << '\n';
}
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 2080 KiB | ||||
2 | Accepted | 3ms | 2252 KiB | ||||
3 | Accepted | 3ms | 3240 KiB | ||||
subtask2 | 40/40 | ||||||
4 | Accepted | 48ms | 10728 KiB | ||||
5 | Accepted | 46ms | 11024 KiB | ||||
6 | Accepted | 48ms | 11212 KiB | ||||
7 | Accepted | 46ms | 11260 KiB | ||||
8 | Accepted | 46ms | 11236 KiB | ||||
9 | Accepted | 46ms | 11236 KiB | ||||
10 | Accepted | 46ms | 11260 KiB | ||||
11 | Accepted | 3ms | 3420 KiB | ||||
subtask3 | 0/60 | ||||||
12 | Accepted | 48ms | 10728 KiB | ||||
13 | Accepted | 46ms | 11024 KiB | ||||
14 | Accepted | 48ms | 11212 KiB | ||||
15 | Accepted | 46ms | 11260 KiB | ||||
16 | Accepted | 46ms | 11236 KiB | ||||
17 | Accepted | 46ms | 11236 KiB | ||||
18 | Accepted | 46ms | 11260 KiB | ||||
19 | Accepted | 3ms | 3420 KiB | ||||
20 | Accepted | 46ms | 11728 KiB | ||||
21 | Accepted | 46ms | 11844 KiB | ||||
22 | Accepted | 46ms | 12012 KiB | ||||
23 | Accepted | 46ms | 11976 KiB | ||||
24 | Accepted | 46ms | 11972 KiB | ||||
25 | Accepted | 48ms | 12076 KiB | ||||
26 | Accepted | 46ms | 12048 KiB | ||||
27 | Accepted | 46ms | 12056 KiB | ||||
28 | Accepted | 41ms | 8436 KiB | ||||
29 | Wrong answer | 48ms | 12252 KiB | ||||
30 | Accepted | 3ms | 4080 KiB | ||||
31 | Accepted | 3ms | 4792 KiB |