Pagini recente » Cod sursa (job #1610223) | Cod sursa (job #1648233) | Cod sursa (job #3227500) | Cod sursa (job #3219151) | Cod sursa (job #1182207)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define DMAX 11
struct Graph{
char inf[DMAX]; // content
char color[DMAX]; // w->g->b
int parent[DMAX], d[DMAX], f[DMAX]; // d = discovered, f = finished
vector<int> Adj[DMAX], AdjT[DMAX]; // Adj list
vector<pair<int, int>> Edge, EdgeT;
} G;
int N, M, time, ok, nrCTC;
vector<int> CTC[DMAX];
list<int> L;
list<int>::iterator l;
void DFS_VISIT(int root){
int i, lg, next;
time++;
G.color[root] = 'g';
G.d[root] = time;
if (ok == 2) CTC[nrCTC].push_back(root);
if(ok==1) lg = G.Adj[root].size();
else lg = G.AdjT[root].size();
for (i = 0; i < lg; i++){
if (ok == 1) next = G.Adj[root][i];
else next = G.AdjT[root][i];
if (G.color[next] == 'w')
DFS_VISIT(next);
}
time++;
G.color[root] = 'b';
G.f[root] = time;
if (ok == 1) L.push_front(root);
}
void DFS(){
int i;
for (i = 1; i <= N; i++){
G.color[i] = 'w';
G.parent[i] = 0;
}
if (ok == 1){
for (i = 1; i <= N; i++){
if (G.color[i] == 'w'){
DFS_VISIT(i);
}
}
}
else{
for (l = L.begin(); l != L.end(); l++)
if (G.color[*l] == 'w'){
nrCTC++;
DFS_VISIT(*l);
}
}
}
int main(){
int i, j, ui, vi, lg;
fin >> N >> M;
for (i = 0; i < M; i++) {
fin >> ui >> vi;
G.Adj[ui].push_back(vi);
G.AdjT[vi].push_back(ui);
G.Edge.push_back(make_pair(ui, vi));
G.EdgeT.push_back(make_pair(vi, ui));
}
ok = 1; DFS();
ok = 2; DFS();
fout << nrCTC << '\n';
for (i = 1; i <= nrCTC; i++){
lg = CTC[i].size();
for (j = 0; j < lg; j++) fout << CTC[i][j] << ' ';
fout << '\n';
}
return 0;
}