10973 - Triangle Counting
Moderator: Board moderators
10973 - Triangle Counting
I couldn't find anything better than O(VE) in this problem. Can anybody explain a better algo please?
Regards
Sanny
Regards
Sanny
-
- New poster
- Posts: 15
- Joined: Thu Oct 16, 2003 7:43 pm
- Location: M
- Contact:
Wrong Solution
Your assumption that the number of edges in such a graph is less than 3*V is wrong. Consider a complete bi-partite graph of V vertices with V/2 vertices on each part. This graph does not have any triangles and has V^2/4 edges.
-
- New poster
- Posts: 15
- Joined: Thu Oct 16, 2003 7:43 pm
- Location: M
- Contact:
I have to accept you are allright. Very nice sample. When i solved this problem, i was thinking what was the worst case for number of triangulesYour assumption that the number of edges in such a graph is less than 3*V is wrong
![:D](./images/smilies/icon_biggrin.gif)
Thank you, Arahimi.
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
This is my code. Is where wrong?
I don't like RTE....
#include <stdio.h>
int main()
{
bool a[3001][3001];
int b,c,d,e,f,g,h;
I don't like RTE....
#include <stdio.h>
int main()
{
bool a[3001][3001];
int b,c,d,e,f,g,h;
Last edited by Wei-Ming Chen on Sun Nov 13, 2005 11:12 am, edited 1 time in total.
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
10973 - Triangle Counting
Code: Select all
#include <iostream>
#include <cstdio>
using namespace std;
bool adj[3001][3001] = {false};
// Graph will be transformed into adjacently matrix.
void reset(); // Reset after each test case.
int main()
{
int t, n, m, a, b, i, j, k;
cin >> t;
while(t--) {
int triangle = 0; // The number of triangle
scanf("%d %d", &n, &m);
for(i = 1; i <= m; i++) {
scanf("%d %d", &a, &b);
adj[a][b] = true;
adj[b][a] = true;
}
// Count triangle in inputed graph.
for(i = 1; i <= m; i++) {
for(j = i + 1; j <= m; j++) {
for(k = j + 1; k <= m; k++) {
if(i != j && i != k && j != k) {
// Are I, J and K connected?
if(adj[i][j] && adj[j][k] && adj[i][k]) {
triangle++;
}
}
}
}
}
cout << triangle << endl;
}
return 0;
}
void reset()
{
int i, j;
for(i = 1; i <= 3000; i++) {
for(j = 1; j <= 3000; j++) {
adj[i][j] = false;
}
}
}
I think 'bool adj[3001][3001]' isn't such big that it raises stack overflow.
Hmm... I don't know why 'Runtime Error'. Please help me!
Do you know why you're living?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
What is your problem? WA or TLE?
the worst case for TLE is a bipartite graph. it has no triangle.
you can write a generator for this kind of input.
the worst case for TLE is a bipartite graph. it has no triangle.
you can write a generator for this kind of input.
Last edited by Moha on Sat Dec 31, 2005 3:31 pm, edited 1 time in total.