879 - Circuit Nets

[CDiMa]

Hi all.
I have a problem understanding the input specification.
The problem text says that the input is terminated by the "end_of_file mark".
Does this refer to each input set?
How do I detect the end of an input set?
My solution ends an input set trying to find a blank line but gets WA.

Thanks in advance for any help...

Ciao!!!

Claudio

[little joey]

Yes, the description is vague in this respect. I made the following assumptions:
1. The input set for each case ends either with a blank line or the EOF (there can be only one EOF, of course).
2. There are no blank lines within the input set for a case.

In other words: each case has one or more lines, each line containing one or more numbers. The last line of the last case may be terminated by an EOF, by NEWLINE+EOF, or even NEWLINE+NEWLINE+EOF, AFAIK.

[Eduard]

Hello.
I have a quastion.

Can there be spaces after the last number of the line???
Thanks.

[CDiMa]

Yes, the description is vague in this respect. I made the following assumptions:
1. The input set for each case ends either with a blank line or the EOF (there can be only one EOF, of course).
2. There are no blank lines within the input set for a case.

In other words: each case has one or more lines, each line containing one or more numbers. The last line of the last case may be terminated by an EOF, by NEWLINE+EOF, or even NEWLINE+NEWLINE+EOF, AFAIK.

Many thanks.
This confirmed that my assumptions were correct.
Actually my program was more tolerant and allowed non numeric characters between two newlines, so that a line with whitespace (I thought that tabs or spaces could be present) was considered blank.
My error was to underestimate the size of input. Just increasing the size of the input buffer helped to get accepted.

Thanks again!

Ciao!!!

Claudio

[CDiMa]

Can there be spaces after the last number of the line???
Thanks.

Actually I don't know if the Judge's input has redundant spaces, but my AC program tolerates them...

Ciao!!!

Claudio

[wos]

Hi,

I am using BFS to transverse the graph, and then search for all those not visited and start the BFS on them again. I count how many times i found vertices that aren't visted, and that is the result. However using this algorithm i get TLE. So i was wondering if there is a faster algorithm to do this ?

[neno_uci]

Which is the largest value for N???

[neno_uci]

What is wrong with my code? I am getting Runtime Error

Code: Select all

Cut after AC

Please help me!!!

[mf]

Which is the largest value for N???

Less than 1048576, that's for certain.

Your program gives wrong answers for the sample input in these forms:

Code: Select all

2

14  1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10

14
  1
11    7     11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10

[neno_uci]

Thanx to mf I solved the problem

[DD]

Hi,

I am using BFS to transverse the graph, and then search for all those not visited and start the BFS on them again. I count how many times i found vertices that aren't visted, and that is the result. However using this algorithm i get TLE. So i was wondering if there is a faster algorithm to do this ?

I think you can try to use union-find disjoint set method, it would be mush faster.

[sushil2006090]

/*Sushil Kumar Singh */
#include <cassert>
#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <ext/numeric>
#include <ext/hash_map>
#include <ext/hash_set>
#include <ext/algorithm>

using namespace std;
using namespace __gnu_cxx;

#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define ii pair<int,int>
#define vs vector<string>
#define all(v) (v).begin(), (v).end()
#define For(i,x) for(int i=0;i<x;i++)
struct node
{
vector<int>adj;
};
bool flag[1048576];
vector<node>v(1048576);
int n;
void dfs(int nod)
{
flag[nod]=true;
for(int i=0;i<v[nod].adj.size();i++)
{
if(!flag[v[nod].adj])
{
dfs(v[nod].adj);
}
}
}
int main()
{
int test;
cin>>test;
string str;
bool mark=true;
while(test--)
{
v.clear();
int num1,num2;
cin>>n;
if(mark==true)
{
mark=false;
}
else
{
cout<<endl;
}
getline(cin,str);
memset(flag,false,sizeof(flag));
while(getline(cin,str))
{

if(str.size()==0) break;
stringstream ss(str);
while(ss>>num1>>num2)
{
v[num1].adj.push_back(num2);
v[num2].adj.push_back(num1);
}
}
int cn=0;
for(int i=1;i<=n;i++)
{
if(!flag)
{
dfs(i);
cn++;
}
}
cout<<cn<<endl;
}
system("pause");
}


donno y i am getting RTE for this code.. can ny1 help me out here??