UVA 10110 - Light, more light

In this problem there will be a number given.

we had to find if the n'th light is on or off? if a light is toggle odd number of time than it is on otherwise its off.

Observations: a number has odd number of factors if and only if it is a perfect square.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<bits/stdc++.h> using namespace std; #define ll long long int main(){ ll n; while(1){ cin>>n; if(n==0){ break; } ///just has to check n is a perfect square or not? because all of the perfect square only ///has odd number of factors. and if number of factors is odd then it will be on. ll xx= sqrt(n); if(xx*xx==n){ cout << "yes\n"; } else cout << "no\n"; } return 0; }

A simple Cycle detection Problem using DFS :: Codeforces 977E

 Problem Link

In this problem several connected components are given, we need to find number of such components with cycle.

A components is contain a cycle if and only if all of its vertices has degree exactly 2.

To find connected components of the graph, we will use  a simple dfs through unvisited nodes. You can learn dfs from here

After that we will check if all the vertices has degree exactly 2 or not.

Official Editorial

Code:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include<bits/stdc++.h> using namespace std; #define pb push_back ///the connected component is a cycle iff the degree of each its vertex equals to 2 const int maxn=200005; vector<int>edge[maxn],connected; int vis[maxn],degree[maxn]; int cnt=0; void dfs(int u){ vis[u]=1; connected.pb(u); for(auto it:edge[u]){ if(vis[it]==0){ dfs(it); } } } int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int u,v; cin>>u>>v; edge[u].pb(v); edge[v].pb(u); degree[u]++; degree[v]++; } for(int i=1;i<=n;i++){ if(vis[i]==0){ connected.clear(); dfs(i); bool ok=1; for(auto it:connected){ if(degree[it]!=2){ ok=0; } } if(ok){ cnt++; } } } cout << cnt << endl; }