Pagini recente » Cod sursa (job #1061882) | Cod sursa (job #241672) | Cod sursa (job #3130808) | Cod sursa (job #1914871) | Cod sursa (job #1810669)
#include <stack>
#include <fstream>
#include <vector>
using namespace std;
vector<int> L[100005];
vector<int> G[100005];
int ind[100005];
int low[100005];
int cur;
stack<int> S;
bool viz[100005];
int k;
vector<int> sol[100005];
void tarjan(int x) {
S.push(x);
viz[x] = true;
cur ++;
ind[x] = low[x] = cur;
for(int i = 0; i < L[x].size(); i ++) {
if(!ind[L[x][i]]) {
tarjan(L[x][i]);
low[x] = min(low[x], low[L[x][i]]);
}
else if(viz[L[x][i]])
low[x] = min(low[x], low[L[x][i]]);
}
if(ind[x] == low[x]) {
k ++;
int nod;
do {
nod = S.top();
S.pop();
viz[nod] = false;
sol[k].push_back(nod);
}
while(nod != x);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, x, y;
f >> n >> m;
for(int i = 1; i <= m; i ++) {
f >> x >> y;
L[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= n; i ++) {
if(ind[i] == 0)
tarjan(i);
}
g << k << "\n";
for(int i = 1; i <= k; i ++) {
for(int j = 0; j < sol[i].size(); j ++)
g << sol[i][j] << " ";
g << "\n";
}
return 0;
}