Add files using upload-large-folder tool

1fd0050 verified 6 months ago

8.24 kB

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
};

static vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    if (N == 1) {
        return vector<vector<int>>(1, vector<int>(1, 1));
    }
    // Build base graph (0-indexed)
    vector<vector<pair<int,int>>> adj(N); // (neighbor, edge id)
    vector<Edge> edges;
    edges.reserve(M);
    vector<int> deg(N,0);
    for (int i = 0; i < M; ++i) {
        int u = A[i]-1, v = B[i]-1;
        edges.push_back({u,v});
        int id = (int)edges.size()-1;
        adj[u].push_back({v,id});
        adj[v].push_back({u,id});
        deg[u]++; deg[v]++;
    }
    // Handle trivial or disconnected cases naively
    // If no edges (should only be valid for N==1), fallback small
    if (M == 0) {
        // Put each color on diagonal in K=N grid but to avoid invalid adjacency
        // we return a 1x1 with color 1 if N==1, else try to place a simple 2x2 valid if possible
        // As a fallback, return N x N all color 1 to avoid invalid adjacencies except coverage (may not satisfy all cases)
        vector<vector<int>> C(1, vector<int>(1, 1));
        return C;
    }
    // Ensure we operate on the largest connected component (simple BFS/DFS)
    vector<int> vis(N, 0);
    vector<int> comp_id(N, -1);
    int cid = 0;
    for (int i = 0; i < N; ++i) if (!vis[i]) {
        queue<int> q; q.push(i); vis[i]=1; comp_id[i]=cid;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(auto [v, id]: adj[u]){
                if(!vis[v]){vis[v]=1; comp_id[v]=cid; q.push(v);}
            }
        }
        cid++;
    }
    // find component with most edges participation
    vector<int> comp_deg(cid,0);
    for (auto &e: edges) {
        comp_deg[comp_id[e.u]]++;
    }
    int best_comp = 0;
    for (int i=1;i<cid;i++) if (comp_deg[i] > comp_deg[best_comp]) best_comp = i;
    // Build subgraph of best component
    vector<int> mapOldToNew(N, -1), mapNewToOld;
    for (int i=0;i<N;i++) if (comp_id[i]==best_comp) {
        mapOldToNew[i] = (int)mapNewToOld.size();
        mapNewToOld.push_back(i);
    }
    int nC = (int)mapNewToOld.size();
    vector<vector<pair<int,int>>> adjC(nC);
    vector<Edge> edgesC;
    edgesC.reserve(M);
    vector<int> degC(nC,0);
    for (auto &e: edges) {
        if (comp_id[e.u]==best_comp) {
            int u = mapOldToNew[e.u], v = mapOldToNew[e.v];
            int id = (int)edgesC.size();
            edgesC.push_back({u,v});
            adjC[u].push_back({v,id});
            adjC[v].push_back({u,id});
            degC[u]++; degC[v]++;
        }
    }
    // Pair odd degree vertices by adding duplicate edges along BFS paths (greedy)
    vector<int> odd;
    for (int i=0;i<nC;i++) if (degC[i]%2) odd.push_back(i);
    auto bfs_path = [&](int s, int t)->vector<int>{
        vector<int> par(nC, -1), pareid(nC, -1);
        queue<int> q; q.push(s); par[s] = s;
        while(!q.empty()){
            int u=q.front();q.pop();
            if(u==t) break;
            for(auto [v,id]: adjC[u]){
                if(par[v]==-1){
                    par[v]=u; pareid[v]=id; q.push(v);
                }
            }
        }
        vector<int> path_eids;
        if(par[t]==-1) return path_eids;
        int cur=t;
        while(cur!=s){
            path_eids.push_back(pareid[cur]);
            cur=par[cur];
        }
        reverse(path_eids.begin(), path_eids.end());
        return path_eids;
    };
    vector<int> unmatched = odd;
    vector<int> usedOdd(nC,0);
    vector<char> paired(nC,0);
    while (!unmatched.empty()) {
        int s = unmatched.back(); unmatched.pop_back();
        if (paired[s]) continue;
        // find nearest unmatched t
        int best_t = -1;
        vector<int> best_path;
        for (int t : unmatched) if (!paired[t]) {
            auto p = bfs_path(s, t);
            if (p.empty()) continue;
            if (best_t==-1 || p.size() < best_path.size()) {
                best_t = t;
                best_path = p;
            }
        }
        if (best_t==-1) {
            // fallback: pair with any other odd (if any) even without path (shouldn't happen in connected comp)
            if (!unmatched.empty()) {
                best_t = unmatched.back(); unmatched.pop_back();
                // if still no path, break
                auto p = bfs_path(s, best_t);
                if (p.empty()) {
                    // cannot fix, break
                    break;
                } else best_path = p;
            } else break;
        } else {
            // remove best_t from unmatched
            for (auto it = unmatched.begin(); it != unmatched.end(); ++it) {
                if (*it == best_t) { unmatched.erase(it); break; }
            }
        }
        // add duplicate edges along path
        int cur = s;
        for (int eid : best_path) {
            int u = edgesC[eid].u, v = edgesC[eid].v;
            // Add a duplicate edge instance (new edge id)
            int id = (int)edgesC.size();
            edgesC.push_back({u,v});
            adjC[u].push_back({v,id});
            adjC[v].push_back({u,id});
            degC[u]++; degC[v]++;
        }
        paired[s]=paired[best_t]=1;
    }
    // Now run Hierholzer on multigraph edgesC
    int start = -1;
    for (int i=0;i<nC;i++) if (!adjC[i].empty()) { start=i; break; }
    if (start == -1) {
        // No edges in best component (shouldn't happen as M>0), fallback
        vector<vector<int>> C(1, vector<int>(1, mapNewToOld.empty()?1:mapNewToOld[0]+1));
        return C;
    }
    int E2 = (int)edgesC.size();
    vector<char> used(E2, 0);
    vector<int> itptr(nC, 0);
    vector<vector<pair<int,int>>> adjIter = adjC;
    vector<int> st;
    vector<int> path;
    st.push_back(start);
    while(!st.empty()){
        int u = st.back();
        while(itptr[u] < (int)adjIter[u].size() && used[adjIter[u][itptr[u]].second]) itptr[u]++;
        if (itptr[u] == (int)adjIter[u].size()) {
            path.push_back(u);
            st.pop_back();
        } else {
            auto [v, id] = adjIter[u][itptr[u]];
            used[id] = 1;
            st.push_back(v);
        }
    }
    if ((int)path.size() < 2) {
        // fallback
        vector<vector<int>> C(1, vector<int>(1, mapNewToOld[start]+1));
        return C;
    }
    reverse(path.begin(), path.end());
    // Build sequence of original vertex labels (1-indexed)
    vector<int> seq;
    seq.reserve(path.size());
    for (int x : path) seq.push_back(mapNewToOld[x] + 1);
    // Remove last if equal to first to make a cyclic sequence edges = L
    if (!seq.empty() && seq.front() == seq.back()) seq.pop_back();
    int L = (int)seq.size();
    if (L <= 0) {
        vector<vector<int>> C(1, vector<int>(1, mapNewToOld[start]+1));
        return C;
    }
    int K = min(L, 240);
    // Build grid with rows rotated by row index, but to ensure coverage attempt to use mod spacing if L > 240 (best effort)
    vector<vector<int>> C(K, vector<int>(K, 1));
    if (L <= 240) {
        for (int r=0;r<K;r++){
            for (int c=0;c<K;c++){
                C[r][c] = seq[(r + c) % L];
            }
        }
    } else {
        // When L > 240, we still fill with wrapping; correctness may not cover all edges but maintains constraints
        for (int r=0;r<K;r++){
            for (int c=0;c<K;c++){
                C[r][c] = seq[(r + c) % L];
            }
        }
    }
    return C;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) {
        return 0;
    }
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<int> A(M), B(M);
        for (int i = 0; i < M; ++i) {
            cin >> A[i] >> B[i];
        }
        vector<vector<int>> C = create_map(N, M, A, B);
        int P = (int)C.size();
        cout << P << "\n";
        for (int i = 0; i < P; ++i) {
            cout << (int)C[i].size() << (i+1<P?' ':'\n');
        }
        cout << "\n";
        for (int i = 0; i < P; ++i) {
            for (int j = 0; j < (int)C[i].size(); ++j) {
                cout << C[i][j] << (j+1==(int)C[i].size()?'\n':' ');
            }
        }
        cout.flush();
    }
    return 0;
}

	#include <bits/stdc++.h>
	using namespace std;

	struct Edge {
	int u, v;
	};

	static vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
	if (N == 1) {
	return vector<vector<int>>(1, vector<int>(1, 1));
	}
	// Build base graph (0-indexed)
	vector<vector<pair<int,int>>> adj(N); // (neighbor, edge id)
	vector<Edge> edges;
	edges.reserve(M);
	vector<int> deg(N,0);
	for (int i = 0; i < M; ++i) {
	int u = A[i]-1, v = B[i]-1;
	edges.push_back({u,v});
	int id = (int)edges.size()-1;
	adj[u].push_back({v,id});
	adj[v].push_back({u,id});
	deg[u]++; deg[v]++;
	}
	// Handle trivial or disconnected cases naively
	// If no edges (should only be valid for N==1), fallback small
	if (M == 0) {
	// Put each color on diagonal in K=N grid but to avoid invalid adjacency
	// we return a 1x1 with color 1 if N==1, else try to place a simple 2x2 valid if possible
	// As a fallback, return N x N all color 1 to avoid invalid adjacencies except coverage (may not satisfy all cases)
	vector<vector<int>> C(1, vector<int>(1, 1));
	return C;
	}
	// Ensure we operate on the largest connected component (simple BFS/DFS)
	vector<int> vis(N, 0);
	vector<int> comp_id(N, -1);
	int cid = 0;
	for (int i = 0; i < N; ++i) if (!vis[i]) {
	queue<int> q; q.push(i); vis[i]=1; comp_id[i]=cid;
	while(!q.empty()){
	int u=q.front();q.pop();
	for(auto [v, id]: adj[u]){
	if(!vis[v]){vis[v]=1; comp_id[v]=cid; q.push(v);}
	}
	}
	cid++;
	}
	// find component with most edges participation
	vector<int> comp_deg(cid,0);
	for (auto &e: edges) {
	comp_deg[comp_id[e.u]]++;
	}
	int best_comp = 0;
	for (int i=1;i<cid;i++) if (comp_deg[i] > comp_deg[best_comp]) best_comp = i;
	// Build subgraph of best component
	vector<int> mapOldToNew(N, -1), mapNewToOld;
	for (int i=0;i<N;i++) if (comp_id[i]==best_comp) {
	mapOldToNew[i] = (int)mapNewToOld.size();
	mapNewToOld.push_back(i);
	}
	int nC = (int)mapNewToOld.size();
	vector<vector<pair<int,int>>> adjC(nC);
	vector<Edge> edgesC;
	edgesC.reserve(M);
	vector<int> degC(nC,0);
	for (auto &e: edges) {
	if (comp_id[e.u]==best_comp) {
	int u = mapOldToNew[e.u], v = mapOldToNew[e.v];
	int id = (int)edgesC.size();
	edgesC.push_back({u,v});
	adjC[u].push_back({v,id});
	adjC[v].push_back({u,id});
	degC[u]++; degC[v]++;
	}
	}
	// Pair odd degree vertices by adding duplicate edges along BFS paths (greedy)
	vector<int> odd;
	for (int i=0;i<nC;i++) if (degC[i]%2) odd.push_back(i);
	auto bfs_path = [&](int s, int t)->vector<int>{
	vector<int> par(nC, -1), pareid(nC, -1);
	queue<int> q; q.push(s); par[s] = s;
	while(!q.empty()){
	int u=q.front();q.pop();
	if(u==t) break;
	for(auto [v,id]: adjC[u]){
	if(par[v]==-1){
	par[v]=u; pareid[v]=id; q.push(v);
	}
	}
	}
	vector<int> path_eids;
	if(par[t]==-1) return path_eids;
	int cur=t;
	while(cur!=s){
	path_eids.push_back(pareid[cur]);
	cur=par[cur];
	}
	reverse(path_eids.begin(), path_eids.end());
	return path_eids;
	};
	vector<int> unmatched = odd;
	vector<int> usedOdd(nC,0);
	vector<char> paired(nC,0);
	while (!unmatched.empty()) {
	int s = unmatched.back(); unmatched.pop_back();
	if (paired[s]) continue;
	// find nearest unmatched t
	int best_t = -1;
	vector<int> best_path;
	for (int t : unmatched) if (!paired[t]) {
	auto p = bfs_path(s, t);
	if (p.empty()) continue;
	if (best_t==-1 \|\| p.size() < best_path.size()) {
	best_t = t;
	best_path = p;
	}
	}
	if (best_t==-1) {
	// fallback: pair with any other odd (if any) even without path (shouldn't happen in connected comp)
	if (!unmatched.empty()) {
	best_t = unmatched.back(); unmatched.pop_back();
	// if still no path, break
	auto p = bfs_path(s, best_t);
	if (p.empty()) {
	// cannot fix, break
	break;
	} else best_path = p;
	} else break;
	} else {
	// remove best_t from unmatched
	for (auto it = unmatched.begin(); it != unmatched.end(); ++it) {
	if (*it == best_t) { unmatched.erase(it); break; }
	}
	}
	// add duplicate edges along path
	int cur = s;
	for (int eid : best_path) {
	int u = edgesC[eid].u, v = edgesC[eid].v;
	// Add a duplicate edge instance (new edge id)
	int id = (int)edgesC.size();
	edgesC.push_back({u,v});
	adjC[u].push_back({v,id});
	adjC[v].push_back({u,id});
	degC[u]++; degC[v]++;
	}
	paired[s]=paired[best_t]=1;
	}
	// Now run Hierholzer on multigraph edgesC
	int start = -1;
	for (int i=0;i<nC;i++) if (!adjC[i].empty()) { start=i; break; }
	if (start == -1) {
	// No edges in best component (shouldn't happen as M>0), fallback
	vector<vector<int>> C(1, vector<int>(1, mapNewToOld.empty()?1:mapNewToOld[0]+1));
	return C;
	}
	int E2 = (int)edgesC.size();
	vector<char> used(E2, 0);
	vector<int> itptr(nC, 0);
	vector<vector<pair<int,int>>> adjIter = adjC;
	vector<int> st;
	vector<int> path;
	st.push_back(start);
	while(!st.empty()){
	int u = st.back();
	while(itptr[u] < (int)adjIter[u].size() && used[adjIter[u][itptr[u]].second]) itptr[u]++;
	if (itptr[u] == (int)adjIter[u].size()) {
	path.push_back(u);
	st.pop_back();
	} else {
	auto [v, id] = adjIter[u][itptr[u]];
	used[id] = 1;
	st.push_back(v);
	}
	}
	if ((int)path.size() < 2) {
	// fallback
	vector<vector<int>> C(1, vector<int>(1, mapNewToOld[start]+1));
	return C;
	}
	reverse(path.begin(), path.end());
	// Build sequence of original vertex labels (1-indexed)
	vector<int> seq;
	seq.reserve(path.size());
	for (int x : path) seq.push_back(mapNewToOld[x] + 1);
	// Remove last if equal to first to make a cyclic sequence edges = L
	if (!seq.empty() && seq.front() == seq.back()) seq.pop_back();
	int L = (int)seq.size();
	if (L <= 0) {
	vector<vector<int>> C(1, vector<int>(1, mapNewToOld[start]+1));
	return C;
	}
	int K = min(L, 240);
	// Build grid with rows rotated by row index, but to ensure coverage attempt to use mod spacing if L > 240 (best effort)
	vector<vector<int>> C(K, vector<int>(K, 1));
	if (L <= 240) {
	for (int r=0;r<K;r++){
	for (int c=0;c<K;c++){
	C[r][c] = seq[(r + c) % L];
	}
	}
	} else {
	// When L > 240, we still fill with wrapping; correctness may not cover all edges but maintains constraints
	for (int r=0;r<K;r++){
	for (int c=0;c<K;c++){
	C[r][c] = seq[(r + c) % L];
	}
	}
	}
	return C;
	}

	int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	if (!(cin >> T)) {
	return 0;
	}
	while (T--) {
	int N, M;
	cin >> N >> M;
	vector<int> A(M), B(M);
	for (int i = 0; i < M; ++i) {
	cin >> A[i] >> B[i];
	}
	vector<vector<int>> C = create_map(N, M, A, B);
	int P = (int)C.size();
	cout << P << "\n";
	for (int i = 0; i < P; ++i) {
	cout << (int)C[i].size() << (i+1<P?' ':'\n');
	}
	cout << "\n";
	for (int i = 0; i < P; ++i) {
	for (int j = 0; j < (int)C[i].size(); ++j) {
	cout << C[i][j] << (j+1==(int)C[i].size()?'\n':' ');
	}
	}
	cout.flush();
	}
	return 0;
	}