CFR 300 B. Coach ( DFS )
Problem - 300B - Codeforces
暴力でやるだけ。実装が下手。
つまらないミスで時間を溶かした。
#include <bits/stdc++.h> using namespace std; const int MAXN = 48 + 2; const int MAXM = MAXN * MAXN / 2; int n, m; vector< int > G[ MAXN ]; struct UnionFind{ int fa[ MAXN ]; void init( int _n ){ for( int i = 1; i <= _n; ++i ) fa[ i ] = i; } int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); } bool unite( int a, int b ){ int x = find( a ); int y = find( b ); if( x == y ) return false; fa[ x ] = y; return true; } } uf; int vis[ MAXN ]; void dfs( int u ){ vis[ u ] = 1; for( int v : G[ u ] ){ int x = uf.find( u ); int y = uf.find( v ); if( x != y ){ uf.unite( u, v ); dfs( v ); } } } void solve(){ uf.init( n ); for( int u = 1; u <= n; ++u ) if( !vis[ u ] ) dfs( u ); vector< int > team[ MAXN ]; for( int u = 1; u <= n; ++u ){ int x = uf.find( u ); team[ x ].push_back( u ); if( team[ x ].size() > 3 ) return (void)puts("-1"); } vector< int > v1, v2, v3; for( int u = 1; u <= n; ++u ){ if( team[ u ].size() == 1 ) v1.push_back( team[ u ][ 0 ] ); if( team[ u ].size() == 2 ) v2.push_back( team[ u ][ 0 ] ), v2.push_back( team[ u ][ 1 ] ); if( team[ u ].size() == 3 ) v3.push_back( team[ u ][ 0 ] ), v3.push_back( team[ u ][ 1 ] ), v3.push_back( team[ u ][ 2 ] ); } // printf("%d %d %d\n", v1.size(), v2.size(), v3.size()); if( v2.size() / 2 > v1.size() ) return (void)puts("-1"); for( int i = 0; i < v2.size(); i += 2 ) printf("%d %d %d\n", v2[ i ], v2[ i + 1 ], v1[ i / 2 ]); for( int i = v2.size() / 2; i < v1.size(); i += 3 ) printf("%d %d %d\n", v1[ i ], v1[ i + 1 ], v1[ i + 2 ]); for( int i = 0; i < v3.size(); i += 3 ) printf("%d %d %d\n", v3[ i ], v3[ i + 1 ], v3[ i + 2 ]); } int main(){ scanf("%d%d", &n, &m); for( int i = 0; i < m; ++i ){ int u, v; scanf("%d%d", &u, &v); G[ u ].push_back( v ); G[ v ].push_back( u ); } solve(); return 0; }