280 - Vertex

[lukai]

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

Code: Select all

1 1
0

isn't it?

[brianfry713]

http://www.uvatoolkit.com/problemssolve.php

[sady]

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);
}
int adj_m[limit][limit], v;
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)
            {
                adj_m[i][j]=inf;
            }
        }
        while( scanf("%d", &src)!= EOF && src )
        {
            while( scanf("%d", &des)!= EOF && des )
            {
                adj_m[src][des]=1;/*reachable*/
            }
        }
        /**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)
            {
                if(adj_m[src][k]==inf)
                {
                    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)
            {
                adj_m[i][j] = min(adj_m[i][j] , max(adj_m[i][k], adj_m[k][j]) );
            }
        }
    }
    return ;
}

[sady]

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

[sady]

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

[mhsn06]

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-----------------

Help please

[brianfry713]

Don't read from a file.

[mhsn06]

Don't read from a file.

thanks for your reply.

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]

why WA ? please help

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]

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?

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??
Thanks in advance
Keep posting !!

[techyvish]

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
    {
        
        vector<vii> adjList;
        vi dfs_linked;
        int v;
        
    public:
        
        vi dfs_num;
        vi reachability;
        set<int> visitvert;
        int nodeToFind;
        
        Graph(int v )
        {
            this->v = v;
            adjList.resize(v+1);
            dfs_num.resize(v+1);
            dfs_linked.resize(v+1);
            reachability.resize(v+1);
        }
        
        void addEdge(int p, int q, int weight)
        {
            adjList[p].push_back(make_pair(q, 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;
        }
        void updateSelfLinks(int p)
        {
            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 )
                    g.addEdge(p, q, 1);
            }
        }
        
        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]

Don't read from file. Did you check input here? http://www.udebug.com/UVa/280

[techyvish]

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]

Please post code that you actually submit with <includes>.

[techyvish]

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
    {
        
        vector<vii> adjList;
        vi dfs_linked;
        int v;
        
    public:
        
        vi dfs_num;
        vi reachability;
        set<int> visitvert;
        int nodeToFind;
        
        Graph(int v )
        {
            this->v = v;
            adjList.resize(v+1);
            dfs_num.resize(v+1);
            dfs_linked.resize(v+1);
            reachability.resize(v+1);
        }
        
        void addEdge(int p, int q, int weight)
        {
            adjList[p].push_back(make_pair(q, 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;
        }
        void updateSelfLinks(int p)
        {
            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 )
                    g.addEdge(p, q, 1);
            }
        }
        
        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;
}