MAXimal :: algo :: �� (original) (raw)

��: 10 Jun 2008 19:24
��: 23 Aug 2011 12:42

��

�� . �� �� �� , �� .

�� , �� (�� ), �� , �� .

�� ��  (��, �� — ��; �� , , , �� , �� , �� ).

�� ��  �� — �� (�� : �� , � ��).

��  �� — ��. �� , �� . �� , �� . �� , �� , � �� , �� (�� — �� ). �� , �� .

��

�� .

��, �� , �.�. �� . �� ? �� -�� , �� . �� , �� , �� , � �� — �� .

�� , � �� ${\rm dfs}(v)$ �� , �� (�� ), �� (�� ) — �� . ��, �� ${\rm dfs}(v)$ �� , �� �� .

�� , � �� "�� " �� . �� — �� , � �� ${\rm dfs}(v)$ �� (�� ). �� , �� -�� , �� , �� (�.�. �� ${\rm dfs}(v)$ , �� ). �� , �� — �� .

��

�� , ��, �� , �.�. �� . �� , �� .

int n; // �� vector g[MAXN]; // �� bool used[MAXN]; vector ans; void dfs (int v) { used[v] = true; for (size_t i=0; i<g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) dfs (to); } ans.push_back (v); } void topological_sort() { for (int i=0; i<n; ++i) used[i] = false; ans.clear(); for (int i=0; i<n; ++i) if (!used[i]) dfs (i); reverse (ans.begin(), ans.end()); }

�� $\rm MAXN$ �� , �� .

�� — �� topological_sort, �� , �� , � �� $\rm ans$ .

�� online judges

�� , � �� :

MAXimal :: algo :: �������������� ���������� (original) (raw)

�������������� ����������

��������

����������

������ � online judges

MAXimal :: algo :: �� (original) (raw)

��

��

��

�� online judges