Хүчтэй чиглэлжүүлэлт¶
Чиглэлгүй графын хүчтэй чиглэлжүүлэлт гэдэг нь түүнийг хүчтэй холбоост граф болгодог, ирмэг бүрд чиглэл олгох явдал юм. Өөрөөр хэлбэл чиглэлжүүлэлт-ийн дараа бид чиглэлтэй ирмэгүүдийг дагаж дурын оройноос дурын орой руу зочлох боломжтой байх ёстой.
Шийдэл¶
Мэдээж үүнийг бүх граф дээр хийж болохгүй. Граф дахь гүүр-ийг авч үзье. Бид түүнд чиглэл олгох ёстой бөгөөд ингэснээрээ энэ гүүрийг зөвхөн нэг чиглэлд "гарч болохоор" болгоно. Энэ нь бид гүүрийн нэг үзүүрээс нөгөө рүү нь очиж чадахгүй гэсэн үг тул графыг хүчтэй холбоост болгож чадахгүй.
Одоо гүүргүй холбоост граф дээрх DFS-ийг авч үзье. Бид орой бүрд зочлох нь тодорхой. Мөн гүүр байхгүй тул бид DFS модны дурын ирмэгийг хасаад ч дор хаяж нэг буцах ирмэг агуулсан замаар ирмэгийн доод талаас дээд тал руу нь очиж чадсан хэвээр байна. Үүнээс дурын оройноос бид DFS модны үндэс рүү очиж чадна гэдэг нь мөрдөнө. Мөн DFS модны үндэснээс бид сонгосон дурын орой руугаа зочилж чадна. Бид хүчтэй чиглэлжүүлэлтийг оллоо!
Өөрөөр хэлбэл гүүргүй холбоост графыг хүчтэй чиглэлжүүлэхийн тулд түүн дээр DFS ажиллуулж, DFS модны ирмэгүүдийг DFS-ийн үндэснээс гадагш, бусад бүх ирмэгийг DFS модонд удмаас өвөг рүү чиглүүл.
Гүүргүй холбоост графууд яг хүчтэй чиглэлжүүлэлттэй графууд байдаг гэсэн үр дүнг Роббинсын теорем гэж нэрлэдэг.
Бодлогын өргөтгөл¶
SCC-ийн тоо хамгийн бага байхаар графын чиглэлжүүлэлтийг олох бодлогыг авч үзье.
Мэдээж графын компонент бүрийг тусад нь авч үзэж болно. Одоо зөвхөн гүүргүй графууд хүчтэй чиглэлжүүлэгдэх боломжтой тул бүх гүүрийг түр зуур хасъя. Бид хэдэн гүүргүй компонент авах ба (яг эхэндээ хэдэн компонент байсан + хэдэн гүүр байсан) тэдгээрийн тус бүрийг хүчтэй чиглэлжүүлж чадна гэдгээ бид мэднэ.
Бидэнд ирмэгүүдийг зөвхөн чиглэлжүүлэхийг зөвшөөрсөн, хасахыг биш, гэвч гүүрүүдийг дурын байдлаар чиглэлжүүлж болох нь тогтоогддог. Мэдээж тэдгээрийг чиглэлжүүлэх хамгийн хялбар арга бол дээр тайлбарласан алгоритмыг өөрчлөлтгүйгээр анхны холбоост компонент бүр дээр ажиллуулах явдал юм.
Implementation¶
Here, the input is n — the number of vertices, m — the number of edges, then m lines describing the edges.
The output is the minimal number of SCCs on the first line and on the second line
a string of m characters,
either > — telling us that the corresponding edge from the input
is oriented from the left to the right vertex (as in the input),
or < — the opposite.
This is a bridge search algorithm modified to also orient the edges, you can as well orient the edges as a first step and count the SCCs on the oriented graph as a second.
vector<vector<pair<int, int>>> adj; // adjacency list - vertex and edge pairs
vector<pair<int, int>> edges;
vector<int> tin, low;
int bridge_cnt;
string orient;
vector<bool> edge_used;
void find_bridges(int v) {
static int time = 0;
low[v] = tin[v] = time++;
for (auto p : adj[v]) {
if (edge_used[p.second]) continue;
edge_used[p.second] = true;
orient[p.second] = v == edges[p.second].first ? '>' : '<';
int nv = p.first;
if (tin[nv] == -1) { // if nv is not visited yet
find_bridges(nv);
low[v] = min(low[v], low[nv]);
if (low[nv] > tin[v]) {
// a bridge between v and nv
bridge_cnt++;
}
} else {
low[v] = min(low[v], tin[nv]);
}
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
adj.resize(n);
tin.resize(n, -1);
low.resize(n, -1);
orient.resize(m);
edges.resize(m);
edge_used.resize(m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
edges[i] = {a, b};
}
int comp_cnt = 0;
for (int v = 0; v < n; v++) {
if (tin[v] == -1) {
comp_cnt++;
find_bridges(v);
}
}
printf("%d\n%s\n", comp_cnt + bridge_cnt, orient.c_str());
}