Medeali's blog

Help needed with problem
By Medeali, history, 10 months ago, In English

` ~~~~~

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.

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Medeali (previous revision, new revision, compare).

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i already got AC on problem just using dfs

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please format your code properly

For example:

#include <bits/stdc++.h>
using namespace std;
int main() {

}

You can do this by putting 3 of ` before and after your code

→ Reply