문제접근
놓쳤던 부분
•
시간초과, 불필요하게 모든 노드를 다 방문 해보려고 함
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int result;
int answer = 0;
vector<bool> visited;
vector<vector<int> > computer;
void dfs(int computerNumber, int depth)
{
if (computer[computerNumber].size() == 0 || visited[computerNumber])
{
result = depth;
if (depth > answer)
answer = depth;
return ;
}
visited[computerNumber] = true;
for (unsigned int i = 0; i < computer[computerNumber].size(); i++)
{
dfs(computer[computerNumber][i], depth + 1);
visited[computer[computerNumber][i]] = false;
}
}
int main(void)
{
int n,m;
vector<int> computerList;
int a, b;
int depth;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
computer.resize(n + 1);
visited.resize(n + 1);
computerList.resize(n + 1);
for (int i = 0; i < m; i++)
{
cin >> a >> b;
computer[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
fill(visited.begin(), visited.end(), false);
depth = 0;
dfs(i, depth + 1);
computerList[i] = result;
}
for (int i = 1; i <= n; i++)
if (computerList[i] == answer)
cout << i << " ";
return (0);
}
C++
복사
코드
3404 KB
3224 ms
#include <iostream>
#include <vector>
using namespace std;
int result;
int answer = 0;
bool visited[10001];
vector<int> computer[10001];
void dfs(int computerNumber)
{
visited[computerNumber] = true;
for (unsigned int i = 0; i < computer[computerNumber].size(); i++)
{
if (visited[computer[computerNumber][i]] == false)
{
dfs(computer[computerNumber][i]);
result++;
}
}
}
int main(void)
{
int n,m;
vector<int> computerList;
int a, b;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
computerList.resize(n + 1);
for (int i = 0; i < m; i++)
{
cin >> a >> b;
computer[b].push_back(a);
}
for (int i = 1; i <= n; i++)
{
result = 0;
fill_n(visited, 10001, false);
dfs(i);
if (result > answer)
answer = result;
computerList[i] = result;
}
for (int i = 1; i <= n; i++)
if (computerList[i] == answer)
cout << i << " ";
return (0);
}
C++
복사