Pagini recente » Cod sursa (job #231691) | Cod sursa (job #280138) | Cod sursa (job #474428) | Cod sursa (job #895730) | Cod sursa (job #1389945)
/*
Keep It Simple!
*/
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int kMaxN = 100005;
vector<int> G[kMaxN],TG[kMaxN];
stack<int> Kos_st;
set<int> CTC_G[kMaxN];
vector<int> ctctest[kMaxN];
int ctc[kMaxN];
int N,M;
int ctc_sz;
void ReadInput()
{
fin >> N >> M;
int x,y;
for(int i=1; i<=M; ++i)
{
fin >> x >> y;
G[x].pb(y);
TG[y].pb(x);
}
}
void FrontDFS(int node)
{
ctc[node] = true;
for(auto it : G[node])
if(!ctc[it])
FrontDFS(it);
Kos_st.push(node);
}
void BackDFS(int node)
{
ctc[node] = ctc_sz;
ctctest[ctc_sz].pb(node);
for(auto it : TG[node])
if(!ctc[it])
BackDFS(it);
}
void Kosaraju()
{
for(int i=1;i<=N;++i)
if(!ctc[i])
FrontDFS(i);
memset(ctc,0,sizeof(ctc));
while(!Kos_st.empty())
{
int node = Kos_st.top();
Kos_st.pop();
if(ctc[node]) continue;
++ctc_sz;
BackDFS(node);
}
}
void BuildTree()
{
for(int x=1; x<=N; ++x)
for(auto y : G[x])
if(ctc[x] != ctc[y])
{
CTC_G[ctc[x]].insert(ctc[y]);
}
}
void Solve()
{
ReadInput();
Kosaraju();
// BuildTree();
fout << ctc_sz << '\n';
for(int i=1; i<=ctc_sz; ++i)
{
for(auto it:ctctest[i])
fout << it << ' ';
fout << '\n';
}
}
int main()
{
Solve();
return 0;
}