Pagini recente » Cod sursa (job #1155296) | Cod sursa (job #1008276) | Cod sursa (job #384973) | Cod sursa (job #5427) | Cod sursa (job #1807667)
#include <fstream>
#include <vector>
using namespace std;
vector<int> L[100005];
vector<int> G[100005];
int sol[100005];
bool viz[100005];
vector<int> q;
int k;
vector<int> s[100005];
void df(int x) {
viz[x] = true;
for(int i = 0; i < L[x].size(); i ++) {
if(!viz[L[x][i]])
df(L[x][i]);
}
q.push_back(x);
}
void dfT(int x) {
sol[x] = k;
for(int i = 0; i < G[x].size(); i ++) {
if(!sol[G[x][i]])
dfT(G[x][i]);
}
}
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(!viz[i])
df(i);
for(; q.size(); q.pop_back()) {
if(!sol[q.back()]) {
k ++;
dfT(q.back());
}
}
for(int i = 1; i <= n; i ++) {
s[sol[i]].push_back(i);
}
g << k << "\n";
for(int i = 1; i <= k; i ++) {
for(int j = 0; j < s[i].size(); j ++)
g << s[i][j] << " ";
g << "\n";
}
return 0;
}