Pagini recente » Cod sursa (job #1244063) | Cod sursa (job #2178402) | Cod sursa (job #1841487) | Cod sursa (job #2110118) | Cod sursa (job #2968292)
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, viz[100001], validnds[100001], mintime[100001], min_nd[100001], cnt = 1, ctcnr, stv_top;
vector <vector<int>> lst,ctc;
stack <int> stv;
ifstream f("ctc.in");
ofstream g("ctc.out");
void DFS(int curnd){
viz[curnd] = 1;
cnt ++;
mintime[curnd] = cnt;
min_nd[curnd] = cnt;
validnds[curnd] = 1;
stv.push(curnd);
for(auto vcnd : lst[curnd]){
if(viz[vcnd] && validnds[vcnd])
min_nd[curnd] = min(min_nd[curnd], mintime[vcnd]);
else if (!viz[vcnd]){
DFS(vcnd);
if(validnds[vcnd])
min_nd[curnd] = min(min_nd[vcnd], min_nd[curnd]);
}
}
if(mintime[curnd] == min_nd[curnd]){
ctcnr ++;
while(true){
stv_top = stv.top();
stv.pop();
validnds[stv_top] = 0;
ctc[ctcnr].push_back(stv_top);
if(stv_top == curnd)
break;
}
}
}
int main(){
f >> n >> m;
lst.assign(n + 1, vector<int>());
for (int i=1; i<=m; i++){
f >> x >> y;
lst[x].push_back(y);
}
ctc.assign(n + 1, vector<int>());
for(int i=1; i<=n; i++)
if(!viz[i])
DFS(i);
g << ctcnr;
for (auto comp : ctc){
for (auto nod : comp)
g << nod << " ";
g << "\n";
}
return 0;
f.close();
g.close();
}