Pagini recente » Cod sursa (job #2602904) | Cod sursa (job #2437273) | Cod sursa (job #1046034) | Cod sursa (job #1585986) | Cod sursa (job #2666414)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
int n, m, i, j, k, start, ord[100003], levMin[100003];
vector<int> vec[100003], comp[100003];
stack<int> stiva;
set<int> s;
void func(int nod) {
int p, x;
ord[nod] = start;
levMin[nod] = start;
start++;
stiva.push(nod);
s.insert(nod);
for(p = 0; p < vec[nod].size(); p++)
if(!ord[vec[nod][p]]) { /// vecinii nevizitati
func(vec[nod][p]); /// func()
levMin[nod] = min(levMin[nod], levMin[vec[nod][p]]); /// actualizez nivelul radacinii
}
else if(s.find(vec[nod][p]) != s.end()) /// daca stiva contine vecinul
levMin[nod] = min(levMin[nod], ord[vec[nod][p]]); /// actualizez nivelul radacinii
if(ord[nod] == levMin[nod])
while(!stiva.empty()) { /// in componenta conexa intra toate nodurile din stiva, care sunt deasupra lui nod
x = stiva.top();
stiva.pop();
s.erase(x);
comp[k].push_back(x);
if(x == nod) {
k++;
break;
}
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
while(m) {
f >> i >> j;
vec[i].push_back(j);
m--;
}
f.close();
k = 0;
start = 1;
for(i = 1; i <= n; i++)
if(!ord[i])
func(i);
g << k << '\n';
for(i = 0; i < k; i++, g << '\n')
for(j = 0; j < comp[i].size(); j++)
g << comp[i][j] << ' ';
g.close();
return 0;
}