Pagini recente » Cod sursa (job #934781) | Cod sursa (job #919400) | Cod sursa (job #1212724) | Cod sursa (job #2609621) | Cod sursa (job #3235895)
//solutie scrisa de Rares Feraru
#include <bits/stdc++.h>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
const int NMAX = 1e5;
vector<int> adj[NMAX+1], adj2[NMAX+1];
vector<int> rez[NMAX+1];
int inv[NMAX+1];
int invers, cnt;
bool marked[NMAX+1];
void dfs(int nod, bool scnd){
if(scnd == true)
rez[cnt].push_back(nod);
marked[nod] = true;
if(scnd == false){
for(int next : adj[nod])
if(!marked[next])
dfs(next, scnd);
invers -= 1;
inv[invers] = nod;
}else{
for(int next : adj2[nod])
if(!marked[next])
dfs(next, scnd);
}
}
int main()
{
int n, m;
f >> n >> m;
invers = n + 1;
//formam listele de adiacenta
for(int i=1; i<=m; i++){
int x, y;
f >> x >> y;
adj[x].push_back(y);
adj2[y].push_back(x);
}
//formam lista inversa de parcurgere a componentelor conexe
for(int i=1; i<=n; i++)
if(!marked[i])
dfs(i, 0);
for(int i=1; i<=n; i++)
marked[i] = false;
//formam elementele tare conexe si le grupam
for(int i=1; i<=n; i++)
if(!marked[inv[i]])
cnt ++, dfs(inv[i], 1);
g << cnt << "\n";
for(int i=1; i<=cnt; i++){
for(int j=0; j<rez[i].size(); j++)
g << rez[i][j] << ' ';
g << "\n";
}
return 0;
}