C++

Forum

 
Vector class problem

nickul (9)
Program doesn't run with vector class matrix(
typedef vector<unsigned int> row;
typedef vector<row> matrix;
matrix a(40000, row(40000));
), but it does with normal array matrix(int a[100][100]). The problem is that I need a big matrix, and this is the only solution I found. Does anyone have any idea why the program runs fine with the normal array, whereas it doesn't even enter the main function with the vector class array? Any help would be appreciated. Thanks in advance!
Here's the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
 
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

ifstream in("drumuri.in");
ofstream out("drumuri.out");

unsigned int n,m;
//typedef vector<bool> row;
//typedef vector<row> matrix;
//matrix a(40000, row(40000));
int a[100][100];

int main();
void op1(unsigned int i, unsigned int j);
void op2(unsigned int i, unsigned int j);
void op3(unsigned int i, unsigned int d);
void op4(unsigned int i);
vector<int> capete(unsigned int i);

int main()
{
	in>>n>>m;

	unsigned int i,k,l;
	int j;
	for (i=1;i<=m;i++) 
	{
		in>>j;
		if(j-4) in>>k>>l;
		else in>>k;
		if(j==1) op1(k-1,l-1);
		if(j==2) op2(k-1,l-1);
		if(j==3) op3(k-1,l);
		if(j==4) op4(k-1);
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++) cout<<a[i][j]<<" ";
		cout<<endl;
	}
	cout.flush();
	system("pause");
	return 0;
}

vector<int> capete(unsigned int i)
{
	vector<int> capat;
	vector<unsigned int> v,v1,v2;
	int nr=1;
	unsigned int k;
	for (k=0;k<n;k++)
		if (a[i][k]==1) v.push_back(k);
	if(v.size()==0) capat.push_back(i);
	else 
		if(v.size()==1) 
		{
			v1.push_back(i);
			v1.push_back(v.at(0));
			while (nr)
			{
				nr--;
				for(k=0;k<n;k++)
					if(a[v1.at(v1.size()-1)][k]==1&&k!=v1.at(v1.size()-2))
					{
						v1.push_back(k);
						nr++;
					}
			}
			capat.push_back(min(i,v1.at(v1.size()-1)));
			capat.push_back(max(i,v1.at(v1.size()-1)));
		}
		else
			if(v.size()==2)
			{
				v1.push_back(i);
				v1.push_back(v.at(0));
				v2.push_back(i);
				v2.push_back(v.at(1));
				while (nr)
				{
					nr--;
					for(k=0;k<n;k++)
						if(a[v1.at(v1.size()-1)][k]==1&&k!=v1.at(v1.size()-2))
						{
							v1.push_back(k);
							nr++;
						}
				}
				while (nr)
				{
					nr--;
					for(k=0;k<n;k++)
						if(a[v2.at(v2.size()-1)][k]==1&&k!=v2.at(v2.size()-2))
						{
							v2.push_back(k);
							nr++;
						}
				}
				capat.push_back(min(v1.at(v1.size()-1),v2.at(v2.size()-1)));
				capat.push_back(max(v1.at(v1.size()-1),v2.at(v2.size()-1)));
			}
	return capat;
}

void op1(unsigned int i, unsigned int j)
{
	vector<int> capat;
	int v1=0,v2=0;
	unsigned int k;
	for (k=0;k<n;k++)
	{
		if(a[i][k]==1)v1++;
		if(a[j][k]==1)v2++;
	}
	if(v1>=2||v2>=2)
	{
		out<<0<<endl;
		return;
	}
	capat=capete(i);
	for(k=0;k<capat.size();k++) 
		if(capat.at(k)==j) 
		{
			out<<0<<endl;
			return;
		}
	a[i][j]=1;
	a[j][i]=1;
	out<<1<<endl;
	return;
}

void op2(unsigned int i, unsigned int j)
{
	if(a[i][j]==0) 
	{
		out<<0<<endl;
		return;
	}
	a[i][j]=0;
	a[j][i]=0;
	out<<1<<endl;
	return;
}

void op3(unsigned int i, unsigned int d)
{
	if(d==0)
	{
		out<<1<<" "<<i+1<<endl;
		return;
	}
	vector<unsigned int> v,v1,v2;
	int nr=1;
	unsigned int k;
	for (k=0;k<n;k++)
		if (a[i][k]==1)	v.push_back(k);
	if(v.size()==0) out<<0<<endl;
	else 
		if(v.size()==1) 
		{
			v1.push_back(i);
			v1.push_back(v.at(0));
			while (nr)
			{
				nr--;
				for(k=0;k<n;k++)
					if(a[v1.at(v1.size()-1)][k]==1&&k!=v1.at(v1.size()-2))
					{
						v1.push_back(k);
						nr++;
					}
			}
			if (v1.at(d)) out<<1<<" "<<v1.at(d)+1<<endl;
			else out<<0<<endl;
		}
		else
			if(v.size()==2)
			{
				v1.push_back(i);
				v1.push_back(v.at(0));
				v2.push_back(i);
				v2.push_back(v.at(1));
				while (nr)
				{
					nr--;
					for(k=0;k<n;k++)
						if(a[v1.at(v1.size()-1)][k]==1&&k!=v1.at(v1.size()-2))
						{
							v1.push_back(k);
							nr++;
						}
				}
				nr=1;
				while (nr)
				{
					nr--;
					for(k=0;k<n;k++)
						if(a[v2.at(v2.size()-1)][k]==1&&k!=v2.at(v2.size()-2))
						{
							v2.push_back(k);
							nr++;
						}
				}
				if (v1.at(d)&&v2.at(d)) out<<2<<" "<<min(v1.at(d),v2.at(d))+1<<" "<<max(v1.at(d),v2.at(d))+1<<endl;
				else if(v1.at(d)) out<<1<<" "<<v1.at(d)+1<<endl;
				else if(v2.at(d)) out<<1<<" "<<v2.at(d)+1<<endl;
				else out<<0<<endl;
			}
}

void op4(unsigned int i)
{
	vector<int> capat;
	capat=capete(i);
	if (capat.size()==1) out<<1<<" "<<capat.at(capat.size()-1)+1<<endl;
	else if(capat.size()==2) out<<2<<" "<<min(capat.at(capat.size()-2),capat.at(capat.size()-1))+1<<" "<<max(capat.at(capat.size()-2),capat.at(capat.size()-1))+1<<endl;
}
}
Last edited on
Fransje (435)
Please use code tags (select the code and press the <> button), this is illegible.
nickul (9)
sorry, I'm new
tfityo (174)
You request at least 40,000*40,000*4 = 6.4GB of memory.
Do you use 64bit OS, does your application is 64bit? In 32bit mode you can address just 2GB (or maybe 4Gb) of memory.

BTW, why do you need so heavy construct?
nickul (9)
I have windows 8 64 bit, visual studio 2012 64 bit.
It's a graph problem.
First you read two numbers, N and M. N is the size of the graph(the number of nodes) and M is the number of operations you need to read from the file and apply to the graph(initially there are no edges in the graph, just nodes). There are 4 kinds of operations: the first one adds an edge, the second one removes an edge, the third one displays all the nodes that are at a distance D from the node specified, and the fourth one lists the end nodes of the road(one edge cannot have more than two neighbors, and there cannot be any cycles in the graph). And the restrictions are:
• 1 ≤ N ≤ 40000
• 1 ≤ M ≤ 400000
• 0 ≤ D ≤ N-1
• 1 ≤ i,j ≤ N
P.S.: the first three operations have two parameters(for the first two it's the nodes, for the third one it's the node and the distance) and the fourth one only has one parameter(the node that's part of the road)
nickul (9)
Also, maximum execution time is 6.5 seconds, available memory is 64 MB, source max size is 20 KB and for 40% of the tests N≤5000 and M≤20000.
tfityo (174)
It means that you cannot have more than M edges.
You may use different representation of the graph, e.g. adjacency list.

If you still want to use adjacency matrix, you can switch to bool instead of int.

All above advises are valid if the problem arises because of huge amount of allocated memory.

What is exact wording of the error message?
nickul (9)
There is no error message, it opens the console and runs and runs and runs(haven't waited for it to stop, it would probably take a lot of time), but if I include <iostream> and put a cout<<1; at the beginning of the main function, it doesn't show 1 in the console, it still stays blank. There is no error, but it doesn't seem to work(or at least it takes too long to declare the matrix, if that's even possible).
tfityo (174)
cout<<1; doesn't print immediately on the screen.
Try to use
cout<<1 << endl; or 
1
2
 
cout<<1;
cout.flush();


Also, please read a short page on graph structures:
http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
nickul (9)
I revised the code(had some mistakes in it), tried replacing int with bool, still doesn't work with the vector class matrix. I also read the page on graph structures, didn't help much... are you suggesting I use something else to define the graph?(other than the adjacency matrix)
nickul (9)
Nevermind, i need to rethink it anyway...
Thanks for your help!
Topic archived. No new replies allowed.