Pagini recente » Cod sursa (job #1554882) | Cod sursa (job #60208) | Cod sursa (job #36340) | Cod sursa (job #2736889) | Cod sursa (job #2199244)
#include <bits/stdc++.h>
#define dimn 100005
std::ifstream f("ctc.in");
std::ofstream g("ctc.out");
int N, M, nc;
std::list <int> adj[dimn];
std::vector <int> comp[dimn];
int ord[dimn], trj_time;
int lowlink[dimn];
std::stack <int> S;
bool is_stacked[dimn];
void tarjan(int start) {
ord[start] = lowlink[start] = trj_time++;
S.push(start); is_stacked[start] = 1;
for (auto vec:adj[start])
if (ord[vec] == -1)
tarjan(vec),
lowlink[start] = std::min(lowlink[start], lowlink[vec]);
else if (is_stacked[vec])
lowlink[start] = std::min(lowlink[start], lowlink[vec]);
if(ord[start] == lowlink[start]) {
int node;
do {
node = S.top(); S.pop();
is_stacked[node] = 0;
comp[nc].push_back(node);
} while(node != start);
nc++;
}
}
void citire() {
f >> N >> M;
for (int i=0, x, y; i<M; i++)
f >> x >> y,
adj[x-1].push_back(y-1);
}
void rezolvare() {
for (int i=0; i<N; i++)
ord[i] = -1;
for (int i=0; i<N; i++)
if(ord[i] == -1)
tarjan(i);
g << nc << "\n";
for (int i=0, j; i<nc; i++) {
for (j=0; j<comp[i].size(); j++)
g << comp[i][j]+1 << " " ;
g << "\n" ;
}
}
int main()
{
citire();
rezolvare();
return 0;
}