Pagini recente » Cod sursa (job #89355) | Cod sursa (job #343017) | Cod sursa (job #1328374) | Cod sursa (job #3171428) | Cod sursa (job #3274325)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100002;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int cnt = 0; ///al cat-elea intra in stiva
vector <vector <int>> v, ctc;
int f[NMAX]; ///0- nevazut inca, 1-vazut, 2-in ctc
int sus[NMAX];
stack <int> s;
void dfs(int start) {
int orig = cnt; ///nivelul original
//cout << start << " " << niv << '\n';
f[start] = 1;
sus[start] = cnt;
s.push(start);
for(auto nod : v[start]) {
if(f[nod] == 2)
continue;
if(!f[nod]) { ///AVEM copil si unde sa ne ducem
cnt++;
dfs(nod);
}
sus[start] = min(sus[start], sus[nod]); ///min ca il vrem pe ala cel mai de SUS
}
if(sus[start] == orig) { ///nu ne putem duce mai sus
//cout << "ctc " << start << '\n';
ctc.push_back(vector <int>());
while(!s.empty() && s.top() != start) {
ctc.back().push_back(s.top());
f[s.top()] = 2;
//cout << s.top() << " ";
s.pop();
}
//cout << start << '\n';
s.pop();
f[start] = 2;
ctc.back().push_back(start);
}
}
int main()
{
int n, m;
cin >> n >> m;
v.resize(n + 1);
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
}
/*for(int i = 1; i <= n; i++) {
cout << "nodul " << i << '\n';
for(auto var : v[i])
cout << var << " ";
cout << '\n';
}*/
for(int i = 1; i <= n; i++) {
if(!f[i]) {
cnt++;
dfs(i);
}
}
cout << ctc.size() << '\n';
for(int i = 0; i < ctc.size(); i++) {
for(auto var : ctc[i])
cout << var << " ";
cout << '\n';
}
return 0;
}