Pagini recente » Cod sursa (job #1710109) | Cod sursa (job #1369581) | Cod sursa (job #881858) | Cod sursa (job #3169318) | Cod sursa (job #2797097)
#include<bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> adjList[100001],adjListTrans[100001],ctc[100001];
vector<int> visited;
queue<int> q;
vector<int> nodes;
void DFS(int x){
int i;
for(i=0;i<adjList[x].size();++i){
if(visited[adjList[x][i]-1]==0){
visited[adjList[x][i]-1]++;
q.push(adjList[x][i]);
//cout<<adjList[x][i]<<' ';
DFS(adjList[x][i]);
}
}
}
void Kosaraju(int x,int node){
int i;
for(i=0;i<adjListTrans[x].size();++i){
if(visited[adjListTrans[x][i]-1]==1){
visited[adjListTrans[x][i]-1]++;
ctc[node].push_back(adjListTrans[x][i]);
Kosaraju(adjListTrans[x][i],node);
}
}
}
int main(){
int n,m,i,a,b;
f>>n>>m;
for(i=0;i<n;++i)
visited.push_back(0);
for(i=0;i<m;++i){
f>>a>>b;
adjList[a].push_back(b);
adjListTrans[b].push_back(a);
}
for(i=0;i<visited.size();++i){
if(visited[i]==0){
visited[i]++;
// cout<<i+1<<' ';
q.push(i+1);
DFS(i+1);
}
}
int count=0;
while(!q.empty()){
int node=q.front();
if(visited[node-1]==1){
visited[node-1]++;
nodes.push_back(node);
ctc[node].push_back(node);
count++;
Kosaraju(node,node);
}
q.pop();
}
g<<count<<'\n';
int j;
for(i=0;i<nodes.size();++i){
for(j=0;j<ctc[nodes[i]].size();++j){
g<<ctc[nodes[i]][j]<<' ';
}
g<<'\n';
}
return 0;
}