` ~~~~~
include <bits/stdc++.h>
using namespace std; typedef long long ll;
define pb push_back
define F first
define S second
void file(){ freopen("input.txt.txt","r",stdin); freopen("output.txt.txt","w",stdout); } int maxer(int a,int b,int c){ return max(a,max(b,c)); } void setio(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
void dfs(int u,vectorgraph[],bool visited[],int colors[],bool &flag){ if(visited[u])return; visited[u]=true; colors[u]=flag+1; flag=!flag; for(auto s:graph[u]){ dfs(s,graph,visited,colors,flag); } } void solve(){ int n,m; cin>>n>>m; vectorgraph[n+1]; vector<pair<int,int>>vp; while(m--){ int a,b; cin>>a>>b; graph[a].pb(b); graph[b].pb(a); vp.pb({a,b}); } bool visited[n+1]; for(int i=1;i<=n;i++) visited[i]=false; int colors[n+1];
} int main() { // file(); solve(); return 0;}
~~~~~
`i am trying to solve this problem https://cses.fi/problemset/task/1668/
My strategy is for each node color its neighbours with different colour ofc every node coloured is counted as visited, i don't know why i got WA.
Auto comment: topic has been updated by Medeali (previous revision, new revision, compare).
Just check whether the graph contains odd length cycle. If no odd length cycle exist, there is always a way to assign colors to each node such that no two adjacent nodes are of same color. Otherwise it is impossible to assign colors.
i already got AC on problem just using dfs
Please format your code properly
For example:
You can do this by putting 3 of ` before and after your code