Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <vector>
- #include <list>
- #include <map>
- #include <set>
- #include <queue>
- #include <deque>
- #include <stack>
- #include <bitset>
- #include <algorithm>
- #include <functional>
- #include <numeric>
- #include <utility>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <ctime>
- #include <memory.h>
- #include <cassert>
- using namespace std;
- #define ll long long
- #define vi vector<int>
- #define pi pair<int,int>
- #define pb push_back
- #define mp make_pair
- #define forn(i,n) for (size_t i = 0; i < n; ++i)
- #define forb(i,n) for (int i = n - 1; i >= 0; --i)
- const double EPS = 1e-9;
- const int MAXN = 100500;
- const int MOD = 1e9 + 7;
- const int MOD1 = 1e9 + 35011;
- const int MOD2 = 1e9 + 18169;
- const int INF = (1 << 30);
- const long long INFl = 1e18;
- int n, m, a, b, tmp[3];
- int color[MAXN];
- queue<int> q;
- vector<int> g[MAXN];
- char used[MAXN];
- void check(int v) {
- tmp[0] = tmp[1] = tmp[2] = 0;
- forn(i,g[v].size()) {
- if(color[g[v][i]] == 0) tmp[0]++;
- if(color[g[v][i]] == 1) tmp[1]++;
- if(color[g[v][i]] == 2) tmp[2]++;
- }
- if (tmp[color[v]] >= 2)
- q.push(v);
- }
- void recolor(int v) {
- q.pop();
- used[v] = true;
- tmp[0] = tmp[1] = tmp[2] = 0;
- forn(i,g[v].size()) {
- if(color[g[v][i]] == 0) tmp[0]++;
- if(color[g[v][i]] == 1) tmp[1]++;
- if(color[g[v][i]] == 2) tmp[2]++;
- }
- for(int i = 0; i < 3; ++i) {
- if (tmp[i] < 2) {
- color[v] = i;
- for (int j = 0; j < g[v].size(); j++)
- check(g[v][j]);
- return;
- }
- }
- }
- int main() {
- #ifdef F0X
- freopen("input.in", "r", stdin);
- #endif
- memset(color, 0, sizeof(int) * MAXN);
- memset(used, false, sizeof(char) * MAXN);
- double st = clock();
- scanf("%d%d", &n, &m);
- forn(i,m) {
- scanf("%d%d", &a, &b);
- g[a].pb(b);
- g[b].pb(a);
- }
- for (int i = 1; i <= n; i++) {
- if (!used[i]) {
- q.push(i);
- while(q.size()) {
- recolor(q.front());
- }
- }
- }
- for (int i = 1; i <= n; ++i) {
- printf("%d ", color[i] + 1);
- }
- #ifdef F0X
- cerr << "Time is " << (clock() - st) / CLOCKS_PER_SEC << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement