Pagini recente » Cod sursa (job #1563578) | Cod sursa (job #223793) | Cod sursa (job #1040326) | Cod sursa (job #2674611) | Cod sursa (job #1385692)
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100000
using namespace std;
typedef vector <int> graf;
typedef stack <int> stiva;
typedef vector <int> ctc;
graf G[MAXN + 1];
int index[MAXN + 1], lowlink[MAXN + 1];
bool in_Stack[MAXN + 1];
stiva S;
vector <ctc> sol;
int ind = 1;
void dfs(int node) {
index[node] = lowlink[node] = ind;
++ind;
in_Stack[node] = true;
S.push(node);
for (graf :: iterator it = G[node].begin() ; it != G[node].end() ; ++it) {
if (!index[*it]) {
dfs(*it);
if (lowlink[*it] < lowlink[node])
lowlink[node] = lowlink[*it];
}
else if (in_Stack[*it])
if (lowlink[*it] < lowlink[node])
lowlink[node] = lowlink[*it];
}
if (index[node] == lowlink[node]) {
ctc comp;
int nd;
do {
nd = S.top();
S.pop();
in_Stack[nd] = false;
comp.push_back(nd);
}
while (nd != node);
sol.push_back(comp);
}
}
int main () {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
for (int i = 0 ; i < m ; ++i) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
}
for (int i = 1 ; i <= n ; ++i)
if (index[i] == 0)
dfs(i);
fout << sol.size() << "\n";
for (int i = 0 ; i < sol.size() ; ++i, fout << "\n")
for (int j = 0 ; j < sol[i].size() ; ++j)
fout << sol[i][j] << " ";
return 0;
}