UVA-11690 using graph theory

1 
#define pb push_back
#define vi vector<int>
using namespace std;
int money[10001]={0};
vi adj[10001];
bool visited[10001];
int sum=0;
void dfs(int node)
{
	sum+=money[node];
	visited[node]=true;
	for(int child:adj[node])
	{
		if(!visited[child])
		{
			visited[child]=true;
			dfs(child);
		}
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<=n;i++)
    	{
    		adj[i].clear();
    		visited[i]=false;
    		money[i]=0;
    	}
    	for(int i=0;i<=n;i++)
    	{
    		cin>>money[i];
    	}
    	for(int i=0;i<m;i++)
    	{
    		int x,y;
    		cin>>x>>y;
    		adj[x].pb(y);
    		adj[y].pb(x);
    	}
    	int flag=0;
    	for(int i=0;i<=n;i++)
    	{
    		if(!visited[i])
    		{
    			dfs(i);
    			if(sum!=0)
    			{
    				flag=1;
    				cout<<"IMPOSSIBLE"<<endl;	
    				break;
    			}
    		}
    	}
    	if(flag==0)
    	{
    		cout<<"POSSIBLE"<<endl;
    	}
    }


    return 0;
}

How can I solve this problem using graph theory?

My idea is to find sum of each node in a cc and check whether if it is zero or not!

2

reset sum=0 for every testcase.

3

still getting WA!

4

for loops was going out of bound while taking money input and in DFS. See the below solution:

#include<bits/stdc++.h>
#define pb push_back
#define vi vector<int>
using namespace std;
int money[10001]={0};
vi adj[10001];
bool visited[10001];
int sum=0;
void dfs(int node)
{
	sum+=money[node];
	// cout << node << " " << sum << endl;
	visited[node]=true;
	// for(auto x:adj[node])
	// 	cout << x << " ";
	// cout << endl;
	for(int child:adj[node])
	{
		// cout << "child is " << child << endl;
		if(!visited[child])
		{
			visited[child]=true;
			dfs(child);
		}
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
    	int n,m;
    	cin>>n>>m;
    	for(int i=0;i<=n;i++)
    	{
    		adj[i].clear();
    		visited[i]=false;
    		money[i]=0;
    	}
    	for(int i=0;i<n;i++)
    	{
    		cin>>money[i];
    	}
    	for(int i=0;i<m;i++)
    	{
    		int x,y;
    		cin>>x>>y;
    		// cout << "here" << endl;
    		adj[x].pb(y);
    		adj[y].pb(x);
    	}
    	int flag=0;
    	sum = 0;
    	for(int i=0;i<n;i++)
    	{
    		if(!visited[i])
    		{
    			dfs(i);
    			// cout << sum << endl;
    			if(sum!=0)
    			{
    				flag=1;
    				cout<<"IMPOSSIBLE"<<endl;	
    				break;
    			}
    		}
    	}
    	if(flag==0)
    	{
    		cout<<"POSSIBLE"<<endl;
    	}
    }


    return 0;
}
1 Like
5

Thank you!