You are not logged in. Please login at www.codechef.com to post your questions!

×

What is wrong with this code for FILLMTR?

include<bits stdc++.h="">

define pb push_back

define mp make_pair

define l long

define ll long long

define f(a,b) for(ll i=a;i<=b;++i)

define fd(a,b) for(ll i=a;i>=b;--i)

define sd(x) scanf("%d",&x)

define s(x) scanf("%lld",&x)

define const 100000

using namespace std; typedef vector<ll> vec; typedef vector<pair<ll,ll> >vp; vector<pair<int,int> >v(const); vector<vector<int> >adj(const); vector<int>vis(const); bool visited[const];

int id[const],sz[const];

int find(int p) { int root = p; while (root != id[root]) root = id[root]; while (p != root) { int newp = id[p]; id[p] = root; p = newp; } return root; };

void merge(int x, int y)
{ int i = find(x); int j = find(y); if (i == j) return;

    if   (sz[i] < sz[j])    { 
    id[i] = j; 
    sz[j] += sz[i]; 
} else  { 
    id[j] = i; 
    sz[i] += sz[j]; 
}
};

bool connected(int x, int y) { return find(x) == find(y); };

bool dfsDetectCycle(int vertex, bool visited[]) { stack<int> s;

s.push(vertex);

while (!s.empty()) {
    int np_vertex = s.top();
    s.pop();
    if (visited[np_vertex]) {
        return true;
    }
    visited[np_vertex] = 1;
       vector<int>::iterator it = adj[np_vertex].begin();
        for (; it != adj[np_vertex].end(); ++it)
            if (!visited[*it])
                s.push(*it);
    }
return false;

};

bool hasCycle() { for (auto it:vis) { if (!visited[it]) { if (dfsDetectCycle(it,visited)) return true; } } return false; };

int main() { int tc; sd(tc); while(tc--) { int n,m,i,j,k; sd(n); v.clear(),adj.clear(); vis.clear(); f(0,n)
{ id[i] = i; sz[i] = 1; }
sd(m); while(m--) { sd(i);sd(j);sd(k); if(k==0) merge(i,j); else v.pb(mp(i,j));} bool flag=0; for(auto it:v) { if(connected(it.first,it.second)) {flag=1;break;} visited[find(it.first)]=false; visited[find(it.second)]=false; vis.pb(it.first),vis.pb(it.second); adj[find(it.first)].pb(find(it.second)); adj[find(it.second)].pb(find(it.first)); } if(flag) cout<<"no\n"; else { if(hasCycle()) cout<<"no\n"; else cout<<"yes\n"; }

}
return 0;

}

asked 17 Sep '17, 15:52

punny_bunny005's gravatar image

1★punny_bunny005
1
accept rate: 0%


its really hard to read your code but what i cans say i that u used graph to solve this problem you can solve this problem using two colouring graph or by using dijoint set however the way u do it i think there might be more than one graph u need to dfc as all the nodes might not be connected forming more than one graph.. here is my solution using dijoint sets

link

answered 17 Sep '17, 16:25

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×7
×1
×1

question asked: 17 Sep '17, 15:52

question was seen: 171 times

last updated: 17 Sep '17, 16:25