## 280 - Vertex

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

### Re: 280 - Vertex Presentation Error?

@brianfry173 what is the output of your given input??

Code: Select all

``````1 1
0
``````
isn't it?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 280 - Vertex Presentation Error?

Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 17
Joined: Sat Dec 07, 2013 8:00 am

### uva 280 - Vertex: why wa??plz help

i checked the sample input of the thread. it gives me correct output.
plz help me to find my bug. thanks in advance.

Code: Select all

``````#include<cstdio>
#define limit 101
#define inf 1e9
inline int max(int a, int b)
{
return ((a>b)?a:b);
}
inline int min(int a, int b)
{
return ((a<b)?a:b);
}
void floyd_warshall();
int main()
{
int  src, des, c,n;
char s[limit];
while( scanf("%d", &v)!=EOF && v )
{
for(int i=1;i<=v;++i)
{
for(int j=1;j<=v;++j)
{
}
}
while( scanf("%d", &src)!= EOF && src )
{
while( scanf("%d", &des)!= EOF && des )
{
}
}
/**end of graph input*/
floyd_warshall();
scanf("%d", &n);
for(int i=0;i<n;++i)
{
scanf("%d", &src);
c=0;
for(int k=1;k<=v;++k)
{
{
s[c]=k+48;
++c;

}
}
s[c]='\0';
printf("%d",c);

for(c=0; s[c];++c)
{
printf(" %c", s[c]);
}
puts("");

}

}
return 0;

}
void floyd_warshall()
{
for(int k=1;k<=v;++k)
{
for(int i=1;i<=v;++i)
{
for(int j=1;j<=v;++j)
{
}
}
}
return ;
}
``````

New poster
Posts: 17
Joined: Sat Dec 07, 2013 8:00 am

### Re: 280 - Vertex

plzzz someone help me.
i couldn't find my mistake.

New poster
Posts: 17
Joined: Sat Dec 07, 2013 8:00 am

### Re: 280 - Vertex

got ac
but any help regarding my mistake in previous code would be appreciated

mhsn06
New poster
Posts: 16
Joined: Tue Apr 01, 2014 7:36 pm

### Re: 280 - Vertex

Hi, I have been trying to find a bug for four/ five hours but failed.

My code outputs

Code: Select all

``````0
0
``````
for input

Code: Select all

``````1
1 1 0
0
1 1
1
0
1 1
0
``````
I can't figure it out why it's showing 0 for second case. It works when the case is the only case in input file.

Code: Select all

``````
vector<vector <int > > graph(105);

graph.clear(); // this causes problem. It will not clear the rows.

----------------Code Removed After AC-----------------
``````

Last edited by mhsn06 on Fri Sep 19, 2014 10:54 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 280 - Vertex

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

mhsn06
New poster
Posts: 16
Joined: Tue Apr 01, 2014 7:36 pm

### Re: 280 - Vertex

brianfry713 wrote:Don't read from a file.

I got the problem. I tried to clear a two dimensional vector with clear(). That's the problem. I used a loop and it's ok now.

battirunner
New poster
Posts: 14
Joined: Fri Aug 15, 2014 3:48 pm

### Re: 280 - Vertex

Code: Select all

``````#include<stdio.h>
int main()
{
//freopen("input.txt","r",stdin);
int a[103][103],b,c,d[103],n,m,i,j,k,initial,enq,u,l;
while(1)
{
scanf("%d",&n);
if(n==0)
{
break;
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
a[i][j]=0;
}
}
int color[103]={0},enque[102]={0};
while(1)
{
scanf("%d",&b);
if(b==0)
{
break;
}
while(1)
{
scanf("%d",&c);
if(c==0)
{
break;
}
a[b][c]=1;
}
}
scanf("%d",&m);
for(i=0;i<m; i++)
{
scanf("%d",&d[i]);
}
for(l=0; l<m; l++)
{
initial=d[l];
enq=0;
enque[enq]=initial;
enq++;
for(k=0; k<enq; k++)
{
u=enque[k];
for(i=1; i<=n; i++)
{
if(color[i]==0 && a[u][i]>0)
{
color[i]=1;
enque[enq]=i;
enq++;
}
}
}
printf("%d",n-enq+1);
for(j=1; j<=n; j++)
{
if(color[j]==0)
{
printf(" %d",j);
}
else
{
color[j]=0;
}
}
printf("\n");
}
}
return 0;
}
``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 280 - Vertex

Mohammad Mahmudur Rahman wrote:You may try this input

Code: Select all

``````5
0
5 1 2 3 4 5
4
1 2 3 4 0
2 3 4 0
3 4 0
0
4 1 2 3 4
``````
Meanwhile, what about using DFS?
Ghust_omega wrote:Hi !! Mohammad Mahmudur Rahman, thanks for the I/O This is the ouput:

Code: Select all

``````5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
1 1
2 1 2
3 1 2 3
4 1 2 3 4

``````
I think that floyd solve the problem too, any suggestions??
Keep posting !!
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

techyvish
New poster
Posts: 9
Joined: Wed Nov 19, 2014 2:32 am

### Re: 280 - Vertex

please help me find my mistake. works with output in forum but returns WA in Online Judge.

Here is my code.

Code: Select all

``````

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<vector<int > > vvi;
typedef vector<string> vs;

#define fin cin

#define VISITED 1
namespace dfs {
class Graph
{

int v;

public:

vi dfs_num;
vi reachability;
set<int> visitvert;
int nodeToFind;

Graph(int v )
{
this->v = v;
dfs_num.resize(v+1);
reachability.resize(v+1);
}

void addEdge(int p, int q, int weight)
{
}

void dfs(int u )
{
if ( u != nodeToFind )
dfs_num[u] = VISITED;

for ( int j = 0 ; j < adjList[u].size() ;j++ )
{
ii v = adjList[u][j];

if ( dfs_num[v.first] != VISITED && v.second == 1 )
{
if ( v.first == nodeToFind )
dfs_num[v.first] = VISITED;
dfs(v.first);
}
}
}

bool isReachable(int from,int to)
{

return false;
}
{
if ( reachability[p] == 1 )
{
dfs_num[p] = VISITED;
}
else
{
dfs_num[p] = !VISITED;
}

}

void clear()
{
dfs_num.clear();
dfs_num.resize(v+1);
}
};
}

//uva280
int main()
//int main()
{
//FILE *fp = freopen("/Users/Shared/codeforces/codeforces/in.txt", "rt", stdin);
fstream fin("/Users/Shared/codeforces/codeforces/uva/dfs.txt");

char sti[1024];
string buffstr;
bool end = false;
while (getline(fin, buffstr) )
{
if ( buffstr == "0")
break;

int numvert = 0;
sscanf(buffstr.c_str(), "%d",&numvert);
dfs::Graph g(numvert);

while (getline(fin, buffstr) )
{
if ( buffstr == "0")
break;
sscanf(buffstr.c_str(), "%[^\n\r]", sti);
stringstream ss(sti);
int p;
ss >> p;
int q;
while (ss>>q) {
if ( q != 0 )
}
}

getline(fin, buffstr);
sscanf(buffstr.c_str(), "%[^\n\r]", sti);
if ( buffstr == "0" ){
end =  true;
break;
}
stringstream A(sti);
int a ;
A >>a;
int b;
while (A >> b) {
g.clear();
g.nodeToFind = b;
g.dfs(b);
string str;
int count = 0;;
for (int i = 1 ; i <= numvert ;i++)
{
if ( !g.dfs_num[i] )
{
str += " ";
stringstream ss;
ss << i ;
string s;
ss >> s;
str += s;
count ++;
}
}

stringstream ss;
ss << count;
string s;
ss >> s;
s += str;
cout << s << endl;
}
}

return 0;
}

``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 280 - Vertex

Don't read from file. Did you check input here? http://www.udebug.com/UVa/280
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

techyvish
New poster
Posts: 9
Joined: Wed Nov 19, 2014 2:32 am

### Re: 280 - Vertex

Thanks lighted for replying , I'm not reading from file when I submit to the online judge.
I tried all inputs from the forum in uDebug and I got the same answers using my code, but I'm not able to find out
which test case fails. Could you please help me to find out ?

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 280 - Vertex

Please post code that you actually submit with <includes>.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

techyvish
New poster
Posts: 9
Joined: Wed Nov 19, 2014 2:32 am

### Re: 280 - Vertex

Hi Sorry lighted,
here is the complete code.

Code: Select all

``````
#include <stdio.h>
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <fstream>
#include <string>

using namespace std;

// Basic macros
#define st          first
#define se          second
#define ALL(x)      (x).begin(), (x).end()
#define ini(a, v)   memset(a, v, sizeof(a))
#define re(i,s,n)  	for(int i=s;i<(n);++i)
#define rep(i,s,n)  for(int i=s;i<=(n);++i)
#define fr(i,n)     re(i,0,n)
#define repv(i,f,t) for(int i = f; i >= t; --i)
#define rev(i,f,t)  repv(i,f - 1,t)
#define frv(i,n)    rev(i,n,0)
#define pu          push_back
#define mp          make_pair
#define sz(x)       (int)(x.size())

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define CLR(a) a.clear()
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++)
#define FORi(i,a,b) for(LET(i,a) ; i<b; i++)
#define repi(i,n) FORi(i,(__typeof(n))0,n)
#define FOR(i,a,b) for(i=a ; i<b; i++)
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pi(n) printf("%d",n)
#define piw(n) printf("%d ",n)
#define pin(n) printf("%d\n",n)
#define sortv(a) sort(a.begin(),a.end())
#define DRT()  int t; cin>>t; while(t--)
#define DRI(n)  int n; cin>>n;
#define DRII(n,m)  int n,m; cin>>n>>m;

const int oo = 2000000009;
const double eps = 1e-9;

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<vector<int > > vvi;
typedef vector<string> vs;

#define fin cin

#define VISITED 1
namespace dfs {
class Graph
{

int v;

public:

vi dfs_num;
vi reachability;
set<int> visitvert;
int nodeToFind;

Graph(int v )
{
this->v = v;
dfs_num.resize(v+1);
reachability.resize(v+1);
}

void addEdge(int p, int q, int weight)
{
}

void dfs(int u )
{
if ( u != nodeToFind )
dfs_num[u] = VISITED;

for ( int j = 0 ; j < adjList[u].size() ;j++ )
{
ii v = adjList[u][j];

if ( dfs_num[v.first] != VISITED && v.second == 1 )
{
if ( v.first == nodeToFind )
dfs_num[v.first] = VISITED;
dfs(v.first);
}
}
}

bool isReachable(int from,int to)
{

return false;
}
{
if ( reachability[p] == 1 )
{
dfs_num[p] = VISITED;
}
else
{
dfs_num[p] = !VISITED;
}

}

void clear()
{
dfs_num.clear();
dfs_num.resize(v+1);
}
};
}

//uva280
int main()
{
//FILE *fp = freopen("/Users/Shared/codeforces/codeforces/in.txt", "rt", stdin);
fstream fin("/Users/Shared/codeforces/codeforces/uva/dfs.txt");

char sti[1024];
string buffstr;
bool end = false;
while (getline(fin, buffstr) )
{
if ( buffstr == "0")
break;

int numvert = 0;
sscanf(buffstr.c_str(), "%d",&numvert);
dfs::Graph g(numvert);

while (getline(fin, buffstr) )
{
if ( buffstr == "0")
break;
sscanf(buffstr.c_str(), "%[^\n\r]", sti);
stringstream ss(sti);
int p;
ss >> p;
int q;
while (ss>>q) {
if ( q != 0 )
}
}

getline(fin, buffstr);
sscanf(buffstr.c_str(), "%[^\n\r]", sti);
if ( buffstr == "0" ){
end =  true;
break;
}
stringstream A(sti);
int a ;
A >>a;
int b;
while (A >> b) {
g.clear();
g.nodeToFind = b;
g.dfs(b);
string str;
int count = 0;;
for (int i = 1 ; i <= numvert ;i++)
{
if ( !g.dfs_num[i] )
{
str += " ";
stringstream ss;
ss << i ;
string s;
ss >> s;
str += s;
count ++;
}
}

stringstream ss;
ss << count;
string s;
ss >> s;
s += str;
cout << s << endl;
}
}

return 0;
}

``````