109362024-04-20 16:40:47k_balintVasútépítéscpp17Wrong answer 40/10048ms12252 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';
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2080 KiB
2Accepted3ms2252 KiB
3Accepted3ms3240 KiB
subtask240/40
4Accepted48ms10728 KiB
5Accepted46ms11024 KiB
6Accepted48ms11212 KiB
7Accepted46ms11260 KiB
8Accepted46ms11236 KiB
9Accepted46ms11236 KiB
10Accepted46ms11260 KiB
11Accepted3ms3420 KiB
subtask30/60
12Accepted48ms10728 KiB
13Accepted46ms11024 KiB
14Accepted48ms11212 KiB
15Accepted46ms11260 KiB
16Accepted46ms11236 KiB
17Accepted46ms11236 KiB
18Accepted46ms11260 KiB
19Accepted3ms3420 KiB
20Accepted46ms11728 KiB
21Accepted46ms11844 KiB
22Accepted46ms12012 KiB
23Accepted46ms11976 KiB
24Accepted46ms11972 KiB
25Accepted48ms12076 KiB
26Accepted46ms12048 KiB
27Accepted46ms12056 KiB
28Accepted41ms8436 KiB
29Wrong answer48ms12252 KiB
30Accepted3ms4080 KiB
31Accepted3ms4792 KiB