Pagini recente » Cod sursa (job #1720524) | Cod sursa (job #1811208) | Cod sursa (job #2130937) | Cod sursa (job #1968305) | Cod sursa (job #2581005)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, sol, cnt, sum, nr;
int head[100005];
vector<int> graph[100005], newG[100005];
stack<int> stk;
bitset<100005> check, inS;
void eliminate_cycles(int now);
int find_head(int node);
void dfs(int now, int where);
int main()
{
fin >> n >> m;
while(m--){
int x, y;
fin >> x >> y;
graph[x].push_back(y);
}
for(int i = 1; i <= n; ++i) head[i] = i;
for(int i = 1; i <= n; ++i){
if(!check[i]){
eliminate_cycles(i);
}
}
/*
for(int i = 1; i <= n; ++i){
if(head[head[i]] != i) find_head(i);
if(i == head[i]) ++cnt;
for(auto next:graph[i]){
if(head[i] == head[next]) continue;
newG[head[i]].push_back(head[next]);
}
}
for(int i = 1; i <= n; ++i){
sort(newG[i].begin(), newG[i].end());
int sz = newG[i].size();
for(int j = 0; j < sz; ++j){
if(j == sz - 1 || newG[i][j] != newG[i][j + 1]){
solve[i][0].push_back(newG[i][j]);
solve[newG[i][j]][1].push_back(i);
++to[i][1];
++to[newG[i][j]][0];
}
}
}
*/
for(int i = 1; i <= n; ++i) {
head[i] = find_head(i);
newG[head[i]].push_back(i);
if(i == head[i]) ++sol;
}
fout << sol << "\n";
for(int i = 1; i <= n; ++i){
if(newG[i].size()){
for(auto node:newG[i]) fout << node << " ";
fout << "\n";
}
}
return 0;
}
void eliminate_cycles(int now){
check[now] = inS[now] = true;
stk.push(now);
for(auto next:graph[now]){
int head1 = find_head(now), head2 = find_head(next);
if(head1 == head2) continue;
if(check[head2] && inS[head2]){
while(stk.top() != head2){
head[stk.top()] = head2;
stk.pop();
}
}
else if(!check[head2]) eliminate_cycles(next);
}
inS[now] = false;
if(stk.top() == now) stk.pop();
}
int find_head(int node){
int cpy = node;
while(head[node] != node) node = head[node];
while(head[cpy] != cpy){
int next = head[cpy];
head[cpy] = node;
cpy = next;
}
return node;
}