SPOJ

Problem Link #include <iostream> #include <vector> using namespace std; bool isParadox; int stmt[101]; // 0 if stmt[i] is false, 1 if true,  -1 if not yet decided int p[101]; // store root of a component void dfs(int s, vector<pair<int,int> > graph[], int root) {       p[s] = root;     for(int i = 0; i < graph[s].size(); i++)     {         int v = graph[s][i].first;         int c = graph[s][i].second;         if(stmt[v] == -1)         {             //if stmt s is true then whatever it says about other stmt is true             //else whatever it says is false. so we have to take its complement             stmt[v] = stmt[s] == 1 ? c : 1 - c;                       dfs(v, graph, ...

Problem Link #include <iostream> #include <vector> #include <queue> using namespace std ; const long N = 1000000 ; long dist[N + 1 ]; void bfs ( long s, long g, long u, long d, long f) { queue< long > q; q. push (s); while (!q. empty ()) { long currentFloor = q. front (); q. pop (); long floorDown = currentFloor - d; long floorUp = currentFloor + u; if (currentFloor == g) { break ; } if (floorDown > 0 && floorDown <= f && dist[floorDown] == - 1 ) { dist[floorDown] = dist[currentFloor] + 1 ; q. push (floorDown); } if (floorUp <= f && dist[floorUp] == - 1 ) { dist[floorUp] = dist[currentFloor] + 1 ; q. push (floorUp); } } } int main () { long f,s, g, u, d;...

Problem Link #include <iostream> #include <queue> using namespace std ; const int N = 10000 ; bool prime[N]; int dist[N]; void sieve () { for ( int i = 2 ; i < N ; i++) { prime[i] = true ; } for ( int i = 3 ; i * i <= N ; i += 2 ) { if (prime[i]) { for ( long k = i * i; k < N ; k += i) { prime[k] = false ; } } } for ( int i = 1000 ; i < N ; i += 2 ) { prime[i] = false ; } } int convertToNum ( int digit[]) { int num = 0 ; for ( int i = 0 ; i <= 3 ; i++) { num = num * 10 + digit[i]; } return num; } void arr ( int digit[], int num) { int i = 3 ; while (num) { int rem = num % 10 ; digit[i--] = rem; num = num / 10 ; } } void bfs ( int n, int m, int ...

Problem Link #include <iostream> #include <queue> #include <vector> #include <stack> #include <cstdio> using namespace std ; const int MOD = 1000000007 ; bool visited[ 10001 ]; stack< int > st; //get topological sorting of DAG void dfs ( int s, vector< int > graph[]) { visited[s] = true ; for ( int i = 0 ; i < graph[s]. size (); i++) { if (!visited[graph[s][i]]) { dfs (graph[s][i], graph); } } st. push (s); } int main () { int d, c, b, s, t, x, y; scanf ( "%d" , &d); while (d--) { scanf ( "%d%d%d%d" , &c,&b,&s,&t); vector< int > graph[c + 1 ]; long dp[c + 1 ]; while (!st. empty ()) { st. pop (); } for ( int i = 0 ; i < c + 1 ; i++) { visited[...

Problem Link #include <iostream> #include <vector> #include <cmath> using namespace std ; bool visited[ 1000001 ]; int maxDistance; int maxDistantVertex; int dfs ( int s, vector< int > graph[], int distance) { visited[s] = true ; if (distance > maxDistance) { maxDistance = distance; maxDistantVertex = s; } for ( int v = 0 ; v < graph[s]. size (); v++) { if (!visited[graph[s][v]]) { dfs (graph[s][v], graph, distance + 1 ); } } return maxDistantVertex; } int main () { int t, n, a, b; cin >> t; while (t--) { cin >> n; vector< int > graph[n]; for ( int i = 0 ; i < n - 1 ; i++) { cin >> a >> b; graph[a]. push_back (b); graph[b]. push_back (a); } fo...

Problem Link #include <iostream> #include <vector> #include <cstring> using namespace std ; int nodesInComponents; const long MOD = 1e9 + 7 ; bool visited[ 100001 ];; void dfs ( int s, vector< int > graph[]) { visited[s] = true ; nodesInComponents++; for ( int v = 0 ; v < graph[s]. size (); v++) { if (!visited[graph[s][v]]) { dfs (graph[s][v], graph); } } } int main () { int t, n, m, i, j, noOfComponents; long numWays; cin >> t; while (t--) { noOfComponents = 0 ; numWays = 1 ; cin >> n >> m; vector< int > graph[n + 1 ]; for ( int k = 0 ; k < n + 1 ; k++) { visited[k] = false ; } for ( int k = 0 ; k < m; k++) { cin >> i >> j; graph[i]. push_bac...

Link #include <iostream> using namespace std; int preIndex = 0; int postIndex = 0; struct node { int data; node *left; node *right; }; int findRootInInorder(int inorder[], int s, int e, int item) { for(int i = s; i <= e; i++) { if(inorder[i] == item) { return i; } } return -1; } node * constructTree(int inorder[], int preorder[], int s, int e) { if(e < s) { return NULL; } //if there is only one element that must be root if(e == s) { node *root = new node(); root->data = inorder[s]; root->left = root->right = NULL; preIndex++; return root; } else { int data = preorder[preIndex++]; node *root = new node(); root->data = data; int index = findRootInInorder(inorder, s, e, data); root->left = constructTree(inorder, preorder, s, index - 1); root->right = constructTree(inorder, preorder, index + 1, e); return root; } } void getPostOrderTraversal(node *...